Skip to main content
Talentd

Allocate Mailboxes - Solution & Explanation

HardArrayMathDynamic ProgrammingSorting14 min readAsked at: Amazon, Goldman Sachs, Google +1
Practice this problem

Problem Statement

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 <= 100
  • 1 <= houses[i] <= 104
  • All the integers of houses are unique.

Approach Overview

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 1: Dynamic Programming Approach

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Try this approach in the editor →

Approach 2: Greedy + Median Approach

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.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Try this approach in the editor →

Approach 3: Dynamic Programming

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Greedy + Median Approach

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Precomputed Median CostO(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 CostO(n^2 * k)O(n^2)When leveraging the median property to compute minimal segment distance efficiently

Video Solution

1478. Allocate Mailboxes | LEETCODE HARD | DYNAMIC PROGRAMMING | LEETCODE • code Explainer • 6,308 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Allocate Mailboxes easy or hard?
Allocate Mailboxes is classified as a hard problem because it requires recognizing the median property for minimizing absolute distance and combining it with dynamic programming over partitions. Managing interval costs and DP transitions correctly is the main challenge.
Allocate Mailboxes Python/Java solution
Python and Java implementations typically sort the houses, precompute the cost matrix using the median index, and then fill a DP table where dp[i][k] represents the minimum distance for the first i houses with k mailboxes. This implementation follows the O(n^2 * k) dynamic programming approach.
How to solve Allocate Mailboxes in O(n)?
An O(n) solution is not feasible for the full problem because you must evaluate multiple ways to partition houses into k groups. The optimal algorithm uses dynamic programming with O(n^2 * k) time after sorting. The median trick reduces segment cost calculation but does not remove the partitioning complexity.
What is the best approach for Allocate Mailboxes?
The most reliable approach is dynamic programming combined with the median distance property. After sorting houses, precompute the cost of serving any range of houses with one mailbox placed at the median. Then use DP to partition houses into k groups, giving a total complexity of O(n^2 * k).
Is Allocate Mailboxes asked at Google/Amazon/Meta?
Allocate Mailboxes is a classic hard dynamic programming problem involving partitioning and median distance optimization. Variants of this problem appear in interviews at large tech companies where candidates must combine sorting, DP, and mathematical insights about medians.
What data structure is used in Allocate Mailboxes?
The solution mainly uses arrays and a 2D dynamic programming table. A precomputed 2D cost matrix stores the minimum distance for serving any house segment with one mailbox, which speeds up the DP transitions.
What is the time complexity of Allocate Mailboxes?
The standard optimal solution runs in O(n^2 * k) time. Sorting houses takes O(n log n), computing the cost table for all house intervals takes O(n^2), and the dynamic programming transitions add another O(n^2 * k).

Ready to solve this problem?

Practice Allocate Mailboxes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays