Scale Engineer

Allocate Mailboxes

Hard
#1365Time: O(k * N^2). Sorting takes O(N log N). The `cost` table precomputation takes O(N^3) with a naive implementation, or O(N^2) with an optimized one. The recursive function has O(k * N) states, and each state computation involves a loop of size up to O(N), leading to a total time of O(k * N^2).Space: O(N^2). We need O(N^2) space for the `cost` table and O(k * N) for the memoization table. Since `k <= N`, the total space is dominated by the `cost` table.
Patterns
MathDynamic Programming
Algorithms
Sorting
Data structures
Array

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses recursion to solve the problem by breaking it down into smaller, overlapping subproblems. We define a function, say solve(i, k), which calculates the minimum cost to serve houses from index i to the end using k mailboxes. To avoid recomputing the same subproblem, we use a memoization table (a 2D array) to store the results. The core idea is to try all possible partitions for the first of the k mailboxes and recursively solve for the rest.

Algorithm

    1. Sort the houses array. Let n be the number of houses.
    1. Precompute a cost[i][j] table storing the minimum cost to serve houses i through j with one mailbox. This cost is sum(|houses[l] - median|) for l from i to j, where the median is houses[(i+j)/2].
    1. Create a memoization table memo[n][k+1], initialized to an indicator like -1.
    1. Define a recursive function solve(i, k):
    • Base case 1: If k=0 and i=n, all houses are covered. Return 0.
    • Base case 2: If k=0 (no mailboxes left) or i=n (no houses left), but not both, it's an impossible state. Return a large value (infinity).
    • Memoization check: If memo[i][k] is not -1, return the stored value.
    • Recursive step: Initialize min_cost = infinity. Iterate j from i to n-1. Calculate current_cost = cost[i][j] + solve(j+1, k-1). Update min_cost = min(min_cost, current_cost).
    • Store min_cost in memo[i][k] and return it.
    1. Call solve(0, k) to get the final answer.

Walkthrough

First, sort the houses array to handle them in positional order. The core of the problem is to partition the sorted houses into k contiguous groups. For any single group of houses, the optimal placement for a mailbox that minimizes the sum of distances is at the median house location.

We can precompute the cost of serving any contiguous group of houses houses[i...j] with one mailbox. Let's call this cost[i][j]. This can be calculated in O(N^2) time.

We define a recursive function solve(i, k) which computes the minimum cost to serve houses from index i to n-1 using k mailboxes. In solve(i, k), we try all possible endpoints j for the first group of houses houses[i...j]. The cost for this choice is cost[i][j] plus the result of the recursive call for the rest of the houses and mailboxes, solve(j+1, k-1). We take the minimum over all possible j.

To make this efficient, we use a 2D array memo[i][k] to store the result of solve(i, k), so each subproblem is solved only once. The final answer is the result of solve(0, k).

class Solution {    int[][] cost;    int[][] memo;    int n;    int[] houses;    final int INF = 1_000_000_000;     public int minDistance(int[] houses, int k) {        this.n = houses.length;        this.houses = houses;        Arrays.sort(this.houses);         // Precompute cost for one mailbox for houses[i...j]        cost = new int[n][n];        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                int median = this.houses[(i + j) / 2];                int currentCost = 0;                for (int l = i; l <= j; l++) {                    currentCost += Math.abs(this.houses[l] - median);                }                cost[i][j] = currentCost;            }        }         memo = new int[n][k + 1];        for (int[] row : memo) {            Arrays.fill(row, -1);        }         return solve(0, k);    }     private int solve(int i, int k) {        if (k == 0 && i == n) return 0;        if (k == 0 || i == n) return INF;        if (memo[i][k] != -1) return memo[i][k];         int minCost = INF;        for (int j = i; j < n; j++) {            minCost = Math.min(minCost, cost[i][j] + solve(j + 1, k - 1));        }         return memo[i][k] = minCost;    }}

Complexity

Time

O(k * N^2). Sorting takes O(N log N). The `cost` table precomputation takes O(N^3) with a naive implementation, or O(N^2) with an optimized one. The recursive function has O(k * N) states, and each state computation involves a loop of size up to O(N), leading to a total time of O(k * N^2).

Space

O(N^2). We need O(N^2) space for the `cost` table and O(k * N) for the memoization table. Since `k <= N`, the total space is dominated by the `cost` table.

Trade-offs

Pros

  • Directly translates the recurrence relation into code, which can be more intuitive.

  • Handles complex state transitions naturally through recursion.

Cons

  • May lead to stack overflow for very deep recursion (not an issue for these constraints).

  • Function call overhead can make it slightly slower than the iterative bottom-up version.

Solutions

class Solution {public  int minDistance(int[] houses, int k) {    Arrays.sort(houses);    int n = houses.length;    int[][] g = new int[n][n];    for (int i = n - 2; i >= 0; --i) {      for (int j = i + 1; j < n; ++j) {        g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i];      }    }    int[][] f = new int[n][k + 1];    final int inf = 1 << 30;    for (int[] e : f) {      Arrays.fill(e, inf);    }    for (int i = 0; i < n; ++i) {      f[i][1] = g[0][i];      for (int j = 2; j <= k && j <= i + 1; ++j) {        for (int p = 0; p < i; ++p) {          f[i][j] = Math.min(f[i][j], f[p][j - 1] + g[p + 1][i]);        }      }    }    return f[n - 1][k];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem