Hard

Allocate Mailboxes

LAB

Given house positions and k mailboxes, return the minimum total distance from each house to its nearest mailbox.

EXAMPLES

Example 1

Input
{
  "houses": [
    1,
    4,
    8,
    10,
    20
  ],
  "k": 3
}

Output
5

FUNCTION SHAPE

houses: intArrayk: int→int

SOLUTION NOTE

Optimal mailbox for a range is at median. DP partitions houses into k groups.

Reveal reference solution +

pythonREFERENCE

def minDistance(self, houses: List[int], k: int) -> int:
    houses.sort()
    n = len(houses)

    # Cost to serve houses[i:j+1] with one mailbox (place at median)
    @cache
    def cost(i, j):
        if i >= j: return 0
        return houses[j] - houses[i] + cost(i + 1, j - 1)

    @cache
    def dp(i, remaining):
        if i == n: return 0
        if remaining == 0: return float('inf')

        res = float('inf')
        for j in range(i, n):
            res = min(res, cost(i, j) + dp(j + 1, remaining - 1))
        return res

    return dp(0, k)

TimeO(n² × k)

SpaceO(n² + n × k)

Open on LeetCode ↗