1478. Allocate Mailboxes
Problem Description
The problem entails finding a way to place k
mailboxes on a street that has houses located at various points, represented by the array houses
. The goal is to minimize the total distance that each house's occupants must travel to reach their nearest mailbox. The array houses[i]
denotes the location of the i
-th house on the street. The key is to allocate these k
mailboxes in a manner that results in the smallest possible sum of distances from each house to its closest mailbox. The challenge is to accomplish this while ensuring that the computed answer is small enough to be represented by a 32-bit integer.
Intuition
To solve this problem, first, we can think about the scenario with only one mailbox (k=1
). The best position for a single mailbox that minimizes the total distance would be the median of the house locations since the median minimizes the sum of absolute deviations. This situation becomes more complex as k
increases.
For the general case with k
mailboxes, we can sort the house locations for more straightforward analysis and applications of dynamic programming (DP). We can treat it as a DP problem, where the state dp[i][j]
represents the minimum total distance for the first i
houses when j
mailboxes are used.
There are two main components of the solution. The first is to calculate the pairwise distance cost g[i][j]
which represents the total distance if a single mailbox served the houses from i
to j
. This approach leverages the fact that if houses are served by a single mailbox, the optimal location is their median, as stated above, and any additional houses paired to this mailbox will add to this distance the difference between the locations.
The second component involves using DP. We initialize our DP table f[][]
considering the first element with the cost with one mailbox and then applying the optimal substructure property of DP. We calculate f[i][j]
, the minimum distance for the first i
houses with j
mailboxes, by checking for all possible positions where the j-1
mailboxes could have been placed before the i
-th house. This would be f[p][j-1] + g[p+1][i]
. We choose the minimum of these to find the optimal distance.
The Python code presented defines the function minDistance
to compute the minimum total distance using this DP approach and returns the value of f[-1][k]
, which represents the minimum total distance using k
mailboxes for all houses.
Learn more about Math, Dynamic Programming and Sorting patterns.
Solution Approach
The solution to this problem utilizes dynamic programming (DP), a method for solving complex problems by breaking them down into simpler subproblems. It involves defining a function or table that keeps track of the results of subproblems to avoid redundant computations. Here’s a step-by-step breakdown of the implementation used in the reference solution provided:
-
Sorting: The first step in the implementation is to sort the input array
houses
. Sorting the houses helps to easily calculate the distance between any two houses and simplify the problem. -
Pre-Calculating Pairwise Distance Costs: The matrix
g
is populated such thatg[i][j]
holds the total distance from the optimal median mailbox to all houses fromhouses[i]
tohouses[j]
. This pre-calculation is pivotal to the efficiency of the algorithm, as it allows quickly accessing the cost of placing a single mailbox for any segment of consecutive houses. -
Dynamic Programming Setup: A 2D array
f
is set up, where each cellf[i][j]
represents the minimal total distance from the firsti
houses withj
mailboxes placed optimally. This DP array is initialized with infinity,inf
, values to represent that, initially, the minimal total distance has not been calculated. -
Filling the DP Table: The table
f
is filled using two nested loops. The outer loop goes over the houses, and the inner loop goes over the possible number of mailboxes. Atf[i][1]
, which represents just 1 mailbox for the firsti
houses, the distance is set as the optimal distance for a single mailbox (g[0][i]
). -
Optimal Substructure: For states where more than one mailbox is used (
j > 1
), another nested loop is used to go over all potential previous placements of mailboxes (p
). For each placement, the algorithm checks the result of having the last mailbox serve houses fromp+1
toi
(f[p][j - 1] + g[p + 1][i]
) and updatesf[i][j]
with the minimum value found. -
Final Result: Finally, the value
f[n-1][k]
will contain the minimal total distance withk
mailboxes for all houses, as the last row of the dynamic programming tablef
represents all houses and thek
th column represents using allk
mailboxes.
In this way, the algorithm ensures that each subproblem is solved optimally, and the solutions of subproblems are combined to solve larger problems. This DP approach, along with careful pre-calculation of distances and optimal substructure exploitation, enables the solution to find the minimal total distance with k
mailboxes efficiently.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Suppose we have an array of house locations houses = [1, 4, 8, 10, 20]
and we want to place k = 2
mailboxes.
Following the steps mentioned in the solution approach:
-
Sorting: The
houses
array is already sorted. -
Pre-Calculating Pairwise Distance Costs: We will create a matrix
g
to store the total distance with a single mailbox for every segment of houses.To fill
g[i][j]
:- The distance when
i == j
is 0 because if there is only one house, no travel is needed. - For
i < j
, calculate the median house and the distance to it from each housei
toj
.
In our example:
g[0][0]
,g[1][1]
,g[2][2]
,g[3][3]
, andg[4][4]
will be 0.- For segment
[1, 4]
, the median is at4
(median of [1, 4]), sog[0][1]
is3
(absolute difference |4-1|). - Calculate similarly for other segments, for example,
g[0][2]
, which is the segment[1, 4, 8]
, where the median is4
, so the total distance is7
(|4-1| + |8-4|).
- The distance when
-
Dynamic Programming Setup: We create a 2D array
f
withn
rows andk+1
columns initialized to infinity.f[i][j]
will eventually represent the minimal total distance for the firsti+1
houses withj
mailboxes. -
Filling the DP Table: We begin to fill the table
f
.For one mailbox and
i
houses,f[i][1]
will be the value ofg[0][i]
:f[0][1] = g[0][0] = 0
f[1][1] = g[0][1] = 3
f[2][1] = g[0][2] = 7
, and so on.
-
Optimal Substructure: Now we update
f
for more than one mailbox.We are aiming to fill
f[4][2]
(for all 5 houses with 2 mailboxes). One mailbox will serve houses0
top
, and the second one will servep+1
to4
.For
p=0
, the cost would bef[0][1] + g[1][4]
. Forp=1
, the cost would bef[1][1] + g[2][4]
. Forp=2
, the cost would bef[2][1] + g[3][4]
, and so on.Select the minimum of these combinations.
-
Final Result: The result we are looking for is the value in
f[4][2]
, which will contain the minimal total distance with 2 mailboxes for all 5 houses.
By computing the subproblems carefully and building upon them, we find the minimal total distance for any given k
and the list of houses.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minDistance(self, houses: List[int], k: int) -> int:
5 # Sort the houses to ensure they are in increasing order of their locations
6 houses.sort()
7 n = len(houses)
8
9 # Precompute the cost of putting one mailbox for the houses in range [i:j+1]
10 # The cost is the sum of distances from houses[i] to each house in the range.
11 costs = [[0] * n for _ in range(n)]
12 for i in range(n - 2, -1, -1):
13 for j in range(i + 1, n):
14 # The cost is built up from the previous smaller range by adding the
15 # distance to the new endpoint house[j].
16 costs[i][j] = costs[i + 1][j - 1] + houses[j] - houses[i]
17
18 # Initialize the dp array with infinite cost. dp[i][j] represents the minimum
19 # total distance from houses[0:i+1] when j mailboxes are used.
20 dp = [[float('inf')] * (k + 1) for _ in range(n)]
21
22 # Calculate minimum distances
23 for i in range(n):
24 # The cost with only one mailbox up to house[i]
25 dp[i][1] = costs[0][i]
26
27 # j represents the number of mailboxes to use
28 for j in range(2, min(k + 1, i + 2)):
29 # Try placing the j-th mailbox after each house[p] and remember minimum total distance
30 for p in range(i):
31 dp[i][j] = min(dp[i][j], dp[p][j - 1] + costs[p + 1][i])
32
33 # Return the minimum distance when all houses are covered by k mailboxes
34 return dp[-1][k]
35
36# Example usage:
37solution = Solution()
38print(solution.minDistance([1, 4, 8, 10, 20], 3)) # Should output the minimum distance
39
1class Solution {
2 public int minDistance(int[] houses, int heaters) {
3 // Sort the houses array
4 Arrays.sort(houses);
5 int numOfHouses = houses.length;
6
7 // Create a distance matrix where g[i][j] is the total distance for grouping houses[i]..houses[j]
8 int[][] distanceMatrix = new int[numOfHouses][numOfHouses];
9 for (int i = numOfHouses - 2; i >= 0; --i) {
10 for (int j = i + 1; j < numOfHouses; ++j) {
11 // Use previously computed values to build up the distance
12 distanceMatrix[i][j] = distanceMatrix[i + 1][j - 1] + houses[j] - houses[i];
13 }
14 }
15
16 // Create a dp table where f[i][j] is the minimum distance for the first i houses with j heaters
17 int[][] dp = new int[numOfHouses][heaters + 1];
18 // Define an 'infinity' value for initial comparison
19 final int INF = 1 << 30;
20
21 // Initialize the dp array with infinity
22 for (int[] row : dp) {
23 Arrays.fill(row, INF);
24 }
25
26 for (int i = 0; i < numOfHouses; ++i) {
27 // The distance for the first i houses and 1 heater is the total distance of range [0, i]
28 dp[i][1] = distanceMatrix[0][i];
29 // Check for all feasible heater positions
30 for (int j = 2; j <= heaters && j <= i + 1; ++j) {
31 for (int p = 0; p < i; ++p) {
32 // Find the best position for the j-th heater, by recursively checking the minimum
33 // distance we found when we placed the last heater at house p
34 dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + distanceMatrix[p + 1][i]);
35 }
36 }
37 }
38 // Answer is the minimum distance to place heaters for all houses
39 return dp[numOfHouses - 1][heaters];
40 }
41}
42
1#include <vector>
2#include <algorithm>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8 int minDistance(vector<int>& houses, int k) {
9 // The size of the houses array.
10 int n = houses.size();
11 // Sorting houses in non-descending order.
12 sort(houses.begin(), houses.end());
13 // cost[i][j] will hold the cost of having one mailbox for the houses[i...j].
14 vector<vector<int>> cost(n, vector<int>(n, 0));
15
16 // Pre-calculate the cost of each range of houses.
17 for (int i = n - 2; i >= 0; --i) {
18 for (int j = i + 1; j < n; ++j) {
19 cost[i][j] = cost[i + 1][j - 1] + houses[j] - houses[i];
20 }
21 }
22
23 // dp[i][j] will hold the minimum total distance for houses[0...i] with j mailboxes.
24 vector<vector<int>> dp(n, vector<int>(k + 1, INT_MAX));
25
26 // Initialize the dp array for the case with 1 mailbox.
27 for (int i = 0; i < n; ++i) {
28 dp[i][1] = cost[0][i];
29 // Check for the minimum distance using 1 to k mailboxes.
30 for (int j = 1; j <= k && j <= i + 1; ++j) {
31 // Calculate the minimum total distance by comparing all possible partitions.
32 for (int p = 0; p < i; ++p) {
33 dp[i][j] = min(dp[i][j], dp[p][j - 1] + cost[p + 1][i]);
34 }
35 }
36 }
37 // The answer is the min total distance for all houses with k mailboxes.
38 return dp[n - 1][k];
39 }
40};
41
1function minDistance(houses: number[], k: number): number {
2 // The size of the houses array.
3 let n: number = houses.length;
4 // Sorting houses in non-descending order.
5 houses.sort((a, b) => a - b);
6 // cost[i][j] will hold the cost of having one mailbox for the houses[i...j].
7 let cost: number[][] = Array.from(Array(n), () => Array(n).fill(0));
8
9 // Pre-calculate the cost of each range of houses.
10 for (let i = n - 2; i >= 0; --i) {
11 for (let j = i + 1; j < n; ++j) {
12 cost[i][j] = cost[i + 1][j - 1] + houses[j] - houses[i];
13 }
14 }
15
16 // dp[i][j] will hold the minimum total distance for houses[0...i] with j mailboxes.
17 let dp: number[][] = Array.from(Array(n), () => Array(k + 1).fill(Number.MAX_SAFE_INTEGER));
18
19 // Initialize the dp array for the case with 1 mailbox.
20 for (let i = 0; i < n; ++i) {
21 dp[i][1] = cost[0][i];
22 // Check for the minimum distance using 1 to k mailboxes.
23 for (let j = 1; j <= k && j <= i + 1; ++j) {
24 // Calculate the minimum total distance by comparing all possible partitions.
25 for (let p = 0; p < i; ++p) {
26 dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + cost[p + 1][i]);
27 }
28 }
29 }
30 // The answer is the minimum total distance for all houses with k mailboxes.
31 return dp[n - 1][k];
32}
33
Time and Space Complexity
Time Complexity
The time complexity of the code can be analyzed by looking at the nested loops and the operations performed within each:
-
The
houses.sort()
call has a time complexity ofO(n log n)
, wheren
is the number of houses, since sorting is typically implemented as a comparison sort. -
The next double loop constructs the
g
matrix, where for each elementg[i][j]
, it calculates the cost of placing one mailbox for the houses ranging from indexi
toj
. This part of the code has two nested loops ranging fromi
ton
andj
fromi+1
ton
, contributing a time complexity ofO(n²)
. -
The last double loop populates the
f
matrix, which represents the minimum cost of placingj
mailboxes for the firsti
houses. The innermost loop is also ranging up ton
, making the time complexity of these loopsO(n² * k)
, wherek
is the number of mailboxes.
Overall, the dominant part of the time complexity comes from the last nested loop, and therefore, the overall time complexity is O(n² * k)
.
Space Complexity
The space complexity can be determined from the space allocated for the dynamic programming matrices:
-
The
g
matrix is ann x n
matrix, which results in a space complexity ofO(n²)
. -
Similarly, the
f
matrix is ann x (k + 1)
matrix, but sincek
could be at mostn
, the space complexity in the worst case would also beO(n²)
.
Taking both matrices into account, the overall space complexity of the algorithm is O(n²)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.