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.
This approach involves using dynamic programming to calculate the minimum total distance for placing mailboxes.
We define dp[i][j] as the minimum distance for houses[0...i] with j mailboxes. The key observation is that to minimize the total distance, the mailbox should be placed near the median of houses in a contiguous segment. We need to precompute the cost of placing a mailbox for every subarray of houses as cost(i, j) = sum of distances from the median of the subarray.
This solution first sorts the houses array. It then precomputes the cost of placing one mailbox between every possible subarray of houses using the median. Then, it fills out a dp table where dp[i][j] captures the minimum distance for the first i houses and j mailboxes, building on previously calculated subproblems to find the overall minimal configuration.
Time Complexity: O(n^3)
Space Complexity: O(n^2)
This approach leverages the property of medians minimizing the sum of absolute deviations. We sort the array of houses and select medians for the segments of houses that should share mailboxes. This method provides a more direct construction but may require additional heuristic checks to ensure optimal distributions.
This JavaScript solution employs a combination of precomputed median-based costs and dynamic programming. By dividing the houses into segments that share a mailbox and computing the minimum distance based on the placement of mailboxes at segment medians, it achieves an efficient allocation strategy.
JavaScript
C#
Time Complexity: O(n^3)
Space Complexity: O(n^2)
We define f[i][j] to represent the minimum total distance between the houses and their nearest mailbox, when placing j mailboxes among the first i+1 houses. Initially, f[i][j] = infty, and the final answer will be f[n-1][k].
We can iterate over the last house p controlled by the j-1-th mailbox, i.e., 0 leq p leq i-1. The j-th mailbox will control the houses in the range [p+1, \dots, i]. Let g[i][j] denote the minimum total distance when placing a mailbox for the houses in the range [i, \dots, j]. The state transition equation is:
$
f[i][j] = min_{0 leq p leq i-1} {f[p][j-1] + g[p+1][i]}
where g[i][j] is computed as follows:
g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i]
The time complexity is O(n^2 times k), and the space complexity is O(n^2), where n$ is the number of houses.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^3) |
| Greedy + Median Approach | Time Complexity: O(n^3) |
| Dynamic Programming | — |
| 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 |
1478. Allocate Mailboxes | LEETCODE HARD | DYNAMIC PROGRAMMING | LEETCODE • code Explainer • 6,082 views views
Watch 7 more video solutions →Practice Allocate Mailboxes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor