Allocate Mailboxes

Houses stand at the integer positions in houses along one street. Install exactly k mailboxes at integer positions so that the sum of every house's distance to its nearest mailbox is as small as possible.
Return that minimum total distance.

Function
minMailboxDistance(houses: int[], k: int) → int

Examples
Example 1
houses = [5,10,15,20]
k = 3
return = 5
Mailboxes at 5, 10, and any median position between 15 and 20 give total distance 5.
Example 2
houses = [6,7,8,12]
k = 2
return = 2
Positions 7 and 12 serve the houses with total distance 2.

Constraints
1 <= houses.length <= 100.
1 <= k <= houses.length.
House positions are distinct integers between 1 and 10000.

The trick has two layers. First, for any group of houses, the best single mailbox sits at the median, so the group cost is the sum of distances to the median. Precompute cost[i][j] for every sorted range in O(n^3) or O(n^2) with a running formula. Second, dp[i][m] is the minimum total for the first i houses using m mailboxes. Transition: dp[i][m] = min over j of dp[j][m-1] + cost[j][i-1]. That's O(n^2 * k), tiny for n = 100. The common pitfall is forgetting to sort first, or assuming mailboxes must sit on a house. The median always works, and with distinct integer positions it lands on one anyway. Also watch the base case: dp[0][0] = 0, everything else infinity. If the recurrence slips under pressure, StealthCoder is your hedge during the live OA.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.