Depot on a Straight Road
MediumSorting & Searching
Problem
Houses stand along a straight road; houses[i] is the position of house i (several houses may share a position). A delivery company will build one depot at any integer position and drive to each house separately.
Return the minimum possible total distance from the depot to all houses, that is the minimum over positions p of the sum of |houses[i] - p|. Aim for average linear time.
Example 1
- Input:
- houses = [1, 6, 2, 9]
- Output:
- 12
Any p between 2 and 6 works: at p = 2 the distances are 1 + 0 + 4 + 7 = 12.
Example 2
- Input:
- houses = [-4, 10, 0]
- Output:
- 14
The depot sits at the median 0: 4 + 10 + 0 = 14.
Constraints
- 1 ≤ houses.length ≤ 10^5
- -10^9 ≤ houses[i] ≤ 10^9
Hint
Show the first hint
Picture the depot sliding one step to the right. How does the total change in terms of houses on each side?
Walkthrough
How to approach it
01Clarify before coding
- Is the depot restricted to a house position? No, any integer, but some house position is always optimal.
- With an even number of houses, which median? Any point between the two middle houses gives the same total, so either middle one works.
- Can the result overflow 32 bits? Yes, up to about 10^14, so use 64-bit integers (safe in JavaScript numbers).
02Brute force
Try every house position as the depot and sum the distances to all houses.
Cost: O(n²): 10^10 operations for n = 10^5. Sorting first and taking the middle element improves this to O(n log n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.