1478. Allocate Mailboxes

HardArrayMathDynamic ProgrammingSorting
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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:

  1. 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.

  2. Pre-Calculating Pairwise Distance Costs: The matrix g is populated such that g[i][j] holds the total distance from the optimal median mailbox to all houses from houses[i] to houses[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.

  3. Dynamic Programming Setup: A 2D array f is set up, where each cell f[i][j] represents the minimal total distance from the first i houses with j mailboxes placed optimally. This DP array is initialized with infinity, inf, values to represent that, initially, the minimal total distance has not been calculated.

  4. 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. At f[i][1], which represents just 1 mailbox for the first i houses, the distance is set as the optimal distance for a single mailbox (g[0][i]).

  5. 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 from p+1 to i (f[p][j - 1] + g[p + 1][i]) and updates f[i][j] with the minimum value found.

  6. Final Result: Finally, the value f[n-1][k] will contain the minimal total distance with k mailboxes for all houses, as the last row of the dynamic programming table f represents all houses and the kth column represents using all k 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example 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:

  1. Sorting: The houses array is already sorted.

  2. 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 house i to j.

    In our example:

    • g[0][0], g[1][1], g[2][2], g[3][3], and g[4][4] will be 0.
    • For segment [1, 4], the median is at 4 (median of [1, 4]), so g[0][1] is 3 (absolute difference |4-1|).
    • Calculate similarly for other segments, for example, g[0][2], which is the segment [1, 4, 8], where the median is 4, so the total distance is 7 (|4-1| + |8-4|).

  3. Dynamic Programming Setup: We create a 2D array f with n rows and k+1 columns initialized to infinity. f[i][j] will eventually represent the minimal total distance for the first i+1 houses with j mailboxes.

  4. Filling the DP Table: We begin to fill the table f.

    For one mailbox and i houses, f[i][1] will be the value of g[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.

  5. 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 houses 0 to p, and the second one will serve p+1 to 4.

    For p=0, the cost would be f[0][1] + g[1][4]. For p=1, the cost would be f[1][1] + g[2][4]. For p=2, the cost would be f[2][1] + g[3][4], and so on.

    Select the minimum of these combinations.

  6. 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
Not Sure What to Study? Take the 2-min Quiz

Depth first search can be used to find whether two components in a graph are connected.

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:

  1. The houses.sort() call has a time complexity of O(n log n), where n is the number of houses, since sorting is typically implemented as a comparison sort.

  2. The next double loop constructs the g matrix, where for each element g[i][j], it calculates the cost of placing one mailbox for the houses ranging from index i to j. This part of the code has two nested loops ranging from i to n and j from i+1 to n, contributing a time complexity of O(nÂČ).

  3. The last double loop populates the f matrix, which represents the minimum cost of placing j mailboxes for the first i houses. The innermost loop is also ranging up to n, making the time complexity of these loops O(nÂČ * k), where k 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:

  1. The g matrix is an n x n matrix, which results in a space complexity of O(nÂČ).

  2. Similarly, the f matrix is an n x (k + 1) matrix, but since k could be at most n, the space complexity in the worst case would also be O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

Math Basics

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

Dynamic Programming Introduction and Patterns

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

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«