Get started

Allocate Mailboxes — Hard Problem & Solution

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

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.

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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue