Allocate Mailboxes

Hard
1063.

Allocate Mailboxes

Allocate Mailboxes is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Microsoft interviews.

houses[i] is the position of the i-th house on a street. Place exactly k mailboxes anywhere along the street.

Return the minimum total distance between each house and its nearest mailbox.

Example 1

Input
houses = [1,4,8,10,20], k = 3
Output
5
Explanation
Mailboxes at 3, 9 and 20 cost 2 + 1 + 1 + 1 + 0.

Example 2

Input
houses = [2,3,5,12,18], k = 2
Output
9
Explanation
One mailbox covers 2, 3, 5 and another covers 12 and 18.

Example 3

Input
houses = [7,4,6,1], k = 1
Output
8

Constraints

  • 1 <= k <= houses.length <= 100
  • 1 <= houses[i] <= 10^4
  • All the integers of houses are unique.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} houses
 * @param {number} k
 * @return {number}
 */
var minDistance = function(houses, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Allocate Mailboxes — Solution in Python, Java & C++

Allocate Mailboxes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Allocate Mailboxes is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Microsoft interviews.

Problem statement

houses[i] is the position of the i-th house on a street. Place exactly k mailboxes anywhere along the street.

Return the minimum total distance between each house and its nearest mailbox.

Example 1

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Mailboxes at 3, 9 and 20 cost 2 + 1 + 1 + 1 + 0.

Example 2

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: One mailbox covers 2, 3, 5 and another covers 12 and 18.

Example 3

Input: houses = [7,4,6,1], k = 1
Output: 8

Constraints

  • 1 <= k <= houses.length <= 100
  • 1 <= houses[i] <= 10^4
  • All the integers of houses are unique.

Hints for Allocate Mailboxes

  1. Hint 1

    Sort the houses. Each mailbox then serves a contiguous block of them.

  2. Hint 2

    For one block, the optimal mailbox sits at the block's median, and the cost is a fixed number you can precompute.

  3. Hint 3

    dp[g][j] = the best cost covering the first j houses with g mailboxes.

How to solve Allocate Mailboxes

Sort the houses; an optimal solution assigns each mailbox a contiguous run. Precompute cost[i][j] — the total distance when a single mailbox serves houses i..j, which is minimised by placing it at the median. Then a partition DP over the number of mailboxes finishes it.

Approach

  1. Sort houses.
  2. For every i <= j, compute cost[i][j] as the sum of |h[t] - median| over the block.
  3. Set dp[0][0] = 0 and dp[g][j] = min over i < j of dp[g-1][i] + cost[i][j-1].
  4. Return dp[k][n].

Why it works

Two facts carry the solution. Contiguity: if a mailbox served a non-contiguous set, some house would be closer to another mailbox — so blocks never interleave, and a partition DP is exhaustive. The median: for absolute deviations on a line the median is the minimiser, which is why each block's cost is a single precomputable number rather than another search.

Complexity

  • Time — O(n³) for the cost table plus O(k · n²) for the DP
  • Space — O(n² + k · n)

Pitfalls

  • The positions arrive unsorted; the contiguity argument only holds after sorting.
  • The median, not the mean, minimises the sum of absolute distances.
  • Exactly k mailboxes must be placed, though two may coincide when k exceeds what is useful.

Reference solution

Python

from typing import List

def minDistance(houses: List[int], k: int) -> int:
    h = sorted(houses)
    n = len(h)
    INF = 10**9
    cost = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            mid = h[(i + j) // 2]
            cost[i][j] = sum(abs(h[t] - mid) for t in range(i, j + 1))
    dp = [[INF] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 0
    for g in range(1, k + 1):
        for j in range(1, n + 1):
            for i in range(j):
                if dp[g - 1][i] == INF:
                    continue
                dp[g][j] = min(dp[g][j], dp[g - 1][i] + cost[i][j - 1])
    return dp[k][n]

Java

public static int minDistance(int[] houses, int k) {
    int[] h = houses.clone();
    Arrays.sort(h);
    int n = h.length;
    final int INF = 1000000000;
    int[][] cost = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int mid = h[(i + j) / 2];
            int total = 0;
            for (int t = i; t <= j; t++) total += Math.abs(h[t] - mid);
            cost[i][j] = total;
        }
    }
    int[][] dp = new int[k + 1][n + 1];
    for (int[] row : dp) Arrays.fill(row, INF);
    dp[0][0] = 0;
    for (int g = 1; g <= k; g++) {
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i < j; i++) {
                if (dp[g - 1][i] == INF) continue;
                dp[g][j] = Math.min(dp[g][j], dp[g - 1][i] + cost[i][j - 1]);
            }
        }
    }
    return dp[k][n];
}

C++

int minDistance(vector<int>& houses, int k) {
    vector<int> h = houses;
    sort(h.begin(), h.end());
    int n = (int) h.size();
    const int INF = 1000000000;
    vector<vector<int>> cost(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int mid = h[(i + j) / 2];
            int total = 0;
            for (int t = i; t <= j; t++) total += abs(h[t] - mid);
            cost[i][j] = total;
        }
    }
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, INF));
    dp[0][0] = 0;
    for (int g = 1; g <= k; g++) {
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i < j; i++) {
                if (dp[g - 1][i] == INF) continue;
                dp[g][j] = min(dp[g][j], dp[g - 1][i] + cost[i][j - 1]);
            }
        }
    }
    return dp[k][n];
}

JavaScript

var minDistance = function(houses, k) {
    var h = houses.slice();
    h.sort(function(a, b) { return a - b; });
    var n = h.length, INF = 1000000000, i, j, t;
    var cost = [];
    for (i = 0; i < n; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(0);
        cost.push(row);
    }
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            var total = 0;
            var mid = h[Math.floor((i + j) / 2)];
            for (t = i; t <= j; t++) total += h[t] > mid ? h[t] - mid : mid - h[t];
            cost[i][j] = total;
        }
    }
    var dp = [];
    for (var g = 0; g <= k; g++) {
        var r = [];
        for (j = 0; j <= n; j++) r.push(INF);
        dp.push(r);
    }
    dp[0][0] = 0;
    for (g = 1; g <= k; g++) {
        for (j = 1; j <= n; j++) {
            for (i = 0; i < j; i++) {
                if (dp[g - 1][i] === INF) continue;
                var cand = dp[g - 1][i] + cost[i][j - 1];
                if (cand < dp[g][j]) dp[g][j] = cand;
            }
        }
    }
    return dp[k][n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming