Allocate Mailboxes — LeetCode 1478 Python Solution

The 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.

Example

Input

houses = [1,4,8,10,20], k = 3

Output

5

Explanation

Allocate mailboxes in position 3, 9 and 20.

Python solution

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]

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1478. Allocate Mailboxes is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems