#1478

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Allocate Mailboxes

Allocate k mailboxes to houses along a street minimizing total distance using dynamic programming with state transitions.

array math dynamic programming sorting

Problem Statement

You are given an array houses where houses[i] represents the position of the ith house along a street, and an integer k representing the number of mailboxes. Your task is to allocate exactly k mailboxes to these houses such that the sum of distances from each house to its nearest mailbox is minimized.

Return the minimum total distance from all houses to their nearest mailbox. The problem assumes all house positions are unique and that the answer will fit within a 32-bit integer. The solution requires carefully handling subarray distance calculations and state transitions to avoid suboptimal allocations.

Examples

Example 1

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

Output: 5

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

Input: houses = [2,3,5,12,18], k = 2

Output: 9

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.

Solution Approach

Sort Houses and Precompute Costs

Begin by sorting the houses array to ensure positions are in order. Precompute the cost for placing a mailbox covering any subarray of houses, typically by placing the mailbox at the median of the subarray, as this minimizes the sum of absolute distances.

Dynamic Programming with State Transitions

Define dp[i][k] as the minimum total distance to cover the first i houses using k mailboxes. Transition by considering every possible partition j < i and adding the precomputed cost of covering houses[j+1..i] with a mailbox, then take the minimum over all j.

Iterative Computation and Optimization

Iterate over the number of mailboxes and positions, updating dp with minimal total distances. Use memoization or prefix sums for subarray costs to reduce redundant calculations. Carefully handle edge cases where k = 1 or k equals the number of houses.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is roughly O(n^2 * k) due to evaluating each subarray for each number of mailboxes, with space complexity O(n * k) for the DP table. Precomputing subarray costs reduces repeated computation but does not change the quadratic nature for n houses.

What Interviewers Usually Probe

Sorting is necessary before applying DP to ensure median calculations minimize distances.
Consider base cases like k=1 or k equal to the number of houses to check your DP setup.
Check whether your DP transitions correctly compute minimum distances over all partitions.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the houses array before computing median costs leads to incorrect minimal distances.
Not precomputing subarray costs can cause TLE for larger n due to repeated absolute sum computations.
Misindexing in DP transitions, especially off-by-one errors in partitions, can return incorrect total distances.

Follow-up variants

Minimizing total distance with mailboxes restricted to integer positions only.
Maximizing the number of houses covered within a distance threshold per mailbox.
Allocating mailboxes where certain houses are mandatory mailbox locations.

FAQ

What is the main pattern used in Allocate Mailboxes?

The problem uses state transition dynamic programming over a sorted array of house positions, focusing on partitioning subarrays.

Why is the median used when k=1?

Placing a single mailbox at the median minimizes the sum of absolute distances to all houses, which is optimal for k=1 segments.

Can I solve Allocate Mailboxes without precomputing subarray costs?

Technically yes, but it leads to redundant computations and may exceed time limits; precomputing improves efficiency significantly.

What are common DP mistakes in this problem?

Common errors include misindexing partitions, not sorting houses, or incorrectly calculating distances in subarrays.

How does GhostInterview handle subarray distance calculations?

It automatically precomputes costs for all subarrays using median placement, then applies DP transitions to guarantee minimal total distance.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the minimum total distance between the houses and their nearest mailbox, when placing $j$ mailboxes among the first $i+1$ houses. Initially, $f[i][j] = \infty$, and the final answer will be $f[n-1][k]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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]

Continue Practicing

#1363 largest multiple of three #1467 probability of a two boxes having the same number of distinct balls #1524 number of sub arrays with odd sum