Watch 8 video solutions for Allocate Mailboxes, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by code Explainer has 6,082 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the array houses where houses[i] is the location of the ith house along a street and an integer k, allocate k mailboxes in the street.
Return the minimum total distance between each house and its nearest mailbox.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: houses = [1,4,8,10,20], k = 3 Output: 5 Explanation: Allocate mailboxes in position 3, 9 and 20. Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5
Example 2:
Input: houses = [2,3,5,12,18], k = 2 Output: 9 Explanation: Allocate mailboxes in position 3 and 14. Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.
Constraints:
1 <= k <= houses.length <= 1001 <= houses[i] <= 104houses are unique.Problem Overview: You are given positions of houses on a street and an integer k. Place exactly k mailboxes so the sum of distances from each house to its nearest mailbox is minimized. Houses lie on a 1D line, so sorting and exploiting median properties becomes the key optimization.
Approach 1: Dynamic Programming with Precomputed Median Cost (O(n^2 * k) time, O(n^2 + n * k) space)
Start by sorting the houses. For any group of houses i..j, the minimum total distance to a single mailbox occurs when the mailbox sits at the median house. Precompute a cost[i][j] table that stores the minimum distance if one mailbox serves houses from i to j. This step takes O(n^2). Then use dynamic programming: let dp[i][m] represent the minimum distance to cover the first i houses with m mailboxes. Transition by trying every split point p, where the last mailbox covers houses p+1..i. The recurrence is dp[i][m] = min(dp[p][m-1] + cost[p+1][i]). This approach systematically explores partitions while leveraging the median distance property, producing the optimal answer.
Approach 2: Greedy + Median Insight (Segment Cost Optimization) (O(n^2 * k) time, O(n^2) space)
The greedy observation is mathematical: for a set of points on a line, the point minimizing total absolute distance is the median. That means every mailbox serving a segment of houses should be placed at the median of that segment. After sorting the array (see sorting), compute segment costs using the median rule instead of testing every location. When evaluating partitions of houses into k groups, each group’s optimal mailbox location becomes deterministic. This removes the need for a search over positions and reduces the problem to choosing the best segmentation. The idea combines properties from array processing and median-based distance minimization from math.
Recommended for interviews: The dynamic programming approach with precomputed median costs is the standard solution interviewers expect. It shows you recognize that the median minimizes absolute distance and can translate that insight into a DP partition problem. Brute-force placement would be prohibitively expensive and unnecessary once the median property is understood. Implementing the DP cleanly, handling indices correctly, and explaining why the median minimizes distance usually demonstrates the depth interviewers look for in hard dynamic programming problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Precomputed Median Cost | O(n^2 * k) | O(n^2 + n * k) | General optimal solution when houses must be split into k segments with minimal total distance |
| Greedy + Median Segment Cost | O(n^2 * k) | O(n^2) | When leveraging the median property to compute minimal segment distance efficiently |