# Allocate Mailboxes
**Difficulty:** HARD
[External](https://leetcode.com/problems/allocate-mailboxes)
Canonical: https://scaleengineer.com/dsa/problems/allocate-mailboxes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/allocate-mailboxes/image0.png) 

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

![](https://assets.glich.co/dsa/allocate-mailboxes/image1.png) 

**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
## Top-Down Dynamic Programming with Memoization
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.
**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.
**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.
### Explanation
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)`.

```java
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;
    }
}
```
### Algorithm
- 1. Sort the `houses` array. Let `n` be the number of houses.
- 2. 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]`.
- 3. Create a memoization table `memo[n][k+1]`, initialized to an indicator like -1.
- 4. 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.
- 5. Call `solve(0, k)` to get the final answer.

## Bottom-Up Dynamic Programming
This is an iterative dynamic programming approach that builds the solution from the smallest subproblems up to the final problem. It uses a 2D DP table to store the minimum cost for covering a certain number of houses with a certain number of mailboxes.
**Time:** O(k * N^2). The three nested loops for `j` (up to `k`), `i` (up to `N`), and `p` (up to `N`) determine the time complexity. · **Space:** O(N^2). O(N^2) for the `cost` table and O(k * N) for the `dp` table.
**Pros:** Avoids recursion overhead and potential stack overflow.; Generally more efficient in practice than the top-down approach due to better memory locality and no function call overhead.
**Cons:** The iterative structure with multiple nested loops can sometimes be harder to reason about than a recursive definition.
### Explanation
This approach avoids recursion by systematically filling a DP table. First, sort the `houses` array.

As before, precompute the `cost[i][j]` table for serving houses `i` to `j` with one mailbox.

We define a DP table `dp[i][j]`, which will store the minimum cost to serve the first `i` houses (i.e., `houses[0...i-1]`) using `j` mailboxes. The table is of size `(n+1) x (k+1)`. `dp[0][0]` is 0, as it costs nothing to serve 0 houses with 0 mailboxes.

We iterate from `j = 1` to `k` (number of mailboxes). For each `j`, we iterate from `i = 1` to `n` (number of houses). To calculate `dp[i][j]`, we consider all possible split points `p`. We assume the last mailbox serves houses from `p` to `i-1`, and the first `j-1` mailboxes serve houses from `0` to `p-1`. The cost is `dp[p][j-1] + cost[p][i-1]`. We take the minimum over all valid `p`.

The final answer is stored in `dp[n][k]`.

```java
class Solution {
    public int minDistance(int[] houses, int k) {
        int n = houses.length;
        Arrays.sort(houses);
        final int INF = 1_000_000_000;

        // cost[i][j]: min cost for houses i to j with one mailbox
        int[][] cost = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int median = houses[(i + j) / 2];
                for (int l = i; l <= j; l++) {
                    cost[i][j] += Math.abs(houses[l] - median);
                }
            }
        }

        // dp[i][j]: min cost for first i houses (0 to i-1) with j mailboxes
        int[][] dp = new int[n + 1][k + 1];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }
        dp[0][0] = 0;

        for (int j = 1; j <= k; j++) { // Number of mailboxes
            for (int i = 1; i <= n; i++) { // Number of houses
                for (int p = 0; p < i; p++) { // Split point
                    // Use j-1 mailboxes for first p houses (0..p-1)
                    // Use 1 mailbox for houses p..i-1
                    if (dp[p][j - 1] != INF) {
                        dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + cost[p][i - 1]);
                    }
                }
            }
        }

        return dp[n][k];
    }
}
```
### Algorithm
- 1. Sort the `houses` array. Let `n` be the number of houses.
- 2. Precompute the `cost[i][j]` table as in the previous approach.
- 3. Initialize a DP table `dp[n+1][k+1]` with a large value (infinity). Set `dp[0][0] = 0`.
- 4. Loop `j` from 1 to `k` (for mailboxes).
- 5. Inside, loop `i` from 1 to `n` (for houses).
- 6. Inside, loop `p` from 0 to `i-1` (for the split point).
- 7. Update `dp[i][j]` using the recurrence: `dp[i][j] = min(dp[i][j], dp[p][j-1] + cost[p][i-1])`.
- 8. The final answer is `dp[n][k]`.

## Dynamic Programming with Divide and Conquer Optimization
This is a highly optimized version of the bottom-up DP. It improves the time complexity by exploiting a special property of the cost function (the Quadrangle Inequality). This property implies that the optimal split point for partitioning the houses is monotonic, which allows us to find it more efficiently using a divide and conquer strategy instead of a full linear scan.
**Time:** O(N^2 + k * N log N). O(N^2) for precomputing the `cost` table. For each of the `k` mailboxes, the divide and conquer part takes O(N log N). Since `k <= N`, the total complexity is often stated as O(N^2). · **Space:** O(N^2). O(N^2) for the `cost` table and O(k * N) for the `dp` table.
**Pros:** Most efficient solution with a time complexity of O(k * N log N) for the DP part.; Significant performance improvement over the standard DP for larger N.
**Cons:** Considerably more complex to understand and implement.; The correctness relies on the Quadrangle Inequality property, which is non-trivial.
### Explanation
The setup is similar: sort `houses`, precompute the `cost` table, and use a `dp` table. The key idea is to optimize the calculation of `dp[i][j] = min_{0 <= p < i} (dp[p][j-1] + cost[p][i-1])`.

Let `opt(i, j)` be the optimal split point `p` for `dp[i][j]`. It can be proven that `opt(i, j) <= opt(i+1, j)`. This is the monotonicity property.

We can leverage this. For a fixed number of mailboxes `j`, we compute the `dp[i][j]` values for all `i` using a recursive helper function, `compute(i_start, i_end, p_start, p_end)`. This function computes `dp` values for `i` in the range `[i_start, i_end]`, given that their optimal split points `p` are in the range `[p_start, p_end]`.

Inside `compute`, we first find the optimal split `p_mid` for the middle element `i_mid = (i_start + i_end) / 2` by searching `p` only in `[p_start, p_end]`. Then, we recursively call `compute` for the left half of `i`'s (`[i_start, i_mid-1]`) with the restricted `p` range `[p_start, p_mid]`, and for the right half (`[i_mid+1, i_end]`) with `p` range `[p_mid, p_end]`. This reduces the O(N) search for the split point to an amortized O(log N) search.

```java
class Solution {
    int[][] cost;
    int[][] dp;
    int n;

    public int minDistance(int[] houses, int k) {
        n = houses.length;
        Arrays.sort(houses);
        final int INF = 1_000_000_000;

        cost = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int median = houses[(i + j) / 2];
                for (int l = i; l <= j; l++) {
                    cost[i][j] += Math.abs(houses[l] - median);
                }
            }
        }

        dp = new int[n + 1][k + 1];
        for (int[] row : dp) Arrays.fill(row, INF);
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i][1] = cost[0][i - 1];
        }

        for (int j = 2; j <= k; j++) {
            compute(j, 1, n, 0, n - 1);
        }

        return dp[n][k];
    }

    private void compute(int j, int i_start, int i_end, int p_start, int p_end) {
        if (i_start > i_end) return;

        int i_mid = i_start + (i_end - i_start) / 2;
        int p_optimal = -1;
        
        // Search for optimal split point p for dp[i_mid][j]
        for (int p = p_start; p <= Math.min(i_mid - 1, p_end); p++) {
            if (dp[p][j - 1] != INF) {
                int current_cost = dp[p][j - 1] + cost[p][i_mid - 1];
                if (current_cost < dp[i_mid][j]) {
                    dp[i_mid][j] = current_cost;
                    p_optimal = p;
                }
            }
        }

        // Recurse on left and right halves with restricted search ranges for p
        compute(j, i_start, i_mid - 1, p_start, p_optimal);
        compute(j, i_mid + 1, i_end, p_optimal, p_end);
    }
}
```
### Algorithm
- 1. Sort `houses` and precompute the `cost[i][j]` table.
- 2. Initialize `dp[n+1][k+1]` table. Set `dp[0][0] = 0`.
- 3. Fill the base case for `j=1`: `dp[i][1] = cost[0][i-1]` for all `i`.
- 4. Loop `j` from 2 to `k`. In each iteration, call a recursive helper `compute(j, 1, n, 0, n-1)`.
- 5. The `compute(j, i_start, i_end, p_start, p_end)` function:
    - If `i_start > i_end`, return.
    - Let `i_mid = (i_start + i_end) / 2`.
    - Find the optimal split point `p_optimal` for `dp[i_mid][j]` by iterating `p` from `p_start` to `min(i_mid-1, p_end)`.
    - Recursively call `compute(j, i_start, i_mid - 1, p_start, p_optimal)`.
    - Recursively call `compute(j, i_mid + 1, i_end, p_optimal, p_end)`.
- 6. The final answer is `dp[n][k]`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minDistance(vector<int> &houses, int k) {
    int n = houses.size();
    sort(houses.begin(), houses.end());
    int g[n][n];
    memset(g, 0, sizeof(g));
    for (int i = n - 2; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i];
      }
    }
    int f[n][k + 1];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i < n; ++i) {
      f[i][1] = g[0][i];
      for (int j = 1; j <= k && j <= i + 1; ++j) {
        for (int p = 0; p < i; ++p) {
          f[i][j] = min(f[i][j], f[p][j - 1] + g[p + 1][i]);
        }
      }
    }
    return f[n - 1][k];
  }
};

```

### Python

```python
class Solution:
    def minDistance(self, houses: List[int], k: int) -> int: houses . sort() n = len(houses) g = [[0] * n for _ in range(n)] for i in range(n - 2, - 1, - 1): for j in range(i + 1, n): g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i] f = [[inf] * (k + 1) for _ in range(n)] for i in range(n): f[i][1] = g[0][i] for j in range(2, min(k + 1, i + 2)): for p in range(i): f[i][j] = min(f[i][j], f[p][j - 1] + g[p + 1][i]) return f[- 1][k]

```