Meeting Point Median Problem

Meeting Point Median Problem — ExecCode Hard DSA Practice

Solve the Meeting Point Median problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Friends stand on a number line at positions arr[i]. They will all walk to one meeting coordinate x, paying |arr[i]-x| each. The best x is a median, and the total cost is a convex piecewise-linear function — the setting slope trick maintains when x is chosen online. Return the minimum total walking cost. Use any median when the length is even; both medians give the same L1 cost. You are given: arr — positions Return minimum sum of absolute deviations. You may pick x equal to one of the people.

Examples

Input {'arr': [1, 2, 3]}; Output 2. Input {'arr': [5]}; Output 0. Input {'arr': [0, 10]}; Output 10

Constraints

Empty array costs 0 Positions may be negative

Practice Meeting Point Median free on ExecCode. Browse DSA problems, topic map, and placement guides.