LeetCode 1478 - Allocate Mailboxes

Here’s a complete, detailed technical solution guide for LeetCode 1478 following your requested format and requirements.

leetcodehardarraymathdynamic-programmingsorting

LeetCode Problem 1478

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Sorting

Solution

Here’s a complete, detailed technical solution guide for LeetCode 1478 following your requested format and requirements.

Problem Understanding

The problem provides a list houses, where each element represents the position of a house along a street. You are asked to allocate exactly k mailboxes to minimize the total distance from each house to its nearest mailbox. The distance metric used is absolute distance along the street, i.e., |house position - mailbox position|.

The input houses is guaranteed to have unique integers, and its length is between 1 and 100. The number of mailboxes k ranges from 1 to the length of houses. Because the answer fits in a 32-bit integer, we do not need to worry about integer overflow in practical implementations.

Edge cases that need careful consideration include scenarios where the number of mailboxes equals the number of houses (each house can have its own mailbox, so the total distance is zero) or when k is 1 (all houses must share a single mailbox, so placing it at the median minimizes distance). The fact that houses can contain large integers (up to 10^4) implies that sorting and absolute difference calculations must be carefully handled.

The key challenge is that naive placement of mailboxes in all possible positions is combinatorially expensive, especially because the number of positions can be large. Therefore, a dynamic programming solution with precomputed costs is necessary.

Approaches

The brute-force approach would be to try all possible placements of k mailboxes along the street. For each placement, calculate the sum of distances from each house to its nearest mailbox. This guarantees the correct answer because we explore all configurations, but it is computationally infeasible. The number of possible placements grows combinatorially with n and k, leading to an exponential time complexity.

The key observation that enables an optimal solution is that for a continuous segment of houses, the optimal position for a single mailbox is at the median of the segment. This reduces the problem to computing the minimum total distance for segments of houses and combining them optimally for k mailboxes. By using dynamic programming, we can efficiently calculate the minimum total distance by considering subproblems: the minimum distance to allocate j mailboxes for the first i houses. Precomputing the cost of placing a mailbox optimally for every contiguous segment of houses further reduces redundant calculations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^k * n) O(1) Try all placements of k mailboxes for n houses. Exponential and infeasible.
Optimal DP O(k * n^2) O(n^2) Use DP with precomputed median costs. Efficient for n <= 100 and k <= n.

Algorithm Walkthrough

  1. Sort Houses: Sorting ensures that the houses are in order. This is crucial because the optimal mailbox for a contiguous segment of houses is at the median, which only works if the houses are ordered.
  2. Precompute Segment Costs: For every pair of indices (i, j) where i <= j, calculate the minimum distance if a mailbox were placed optimally for the segment houses[i..j]. Place the mailbox at the median house in that segment. Store these costs in a 2D array cost[i][j].
  3. Initialize DP Table: Define dp[i][k] as the minimum total distance to allocate k mailboxes for the first i houses. Initialize dp[0][0] = 0 since zero houses with zero mailboxes costs zero.
  4. Populate DP Table: For each i from 1 to n, and for each number of mailboxes m from 1 to k, compute dp[i][m] as the minimum of dp[j][m-1] + cost[j][i-1] for all j from 0 to i-1. This represents placing the last mailbox optimally for the segment houses[j..i-1] and using m-1 mailboxes for the preceding houses.
  5. Return Result: After filling the DP table, dp[n][k] contains the minimum total distance for n houses with k mailboxes.

Why it works: The DP formulation guarantees that at every step, the solution for i houses and m mailboxes uses the optimal solution for all previous subproblems with fewer mailboxes. The segment cost using the median ensures local optimality, and combining it in DP ensures global optimality.

Python Solution

from typing import List

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        n = len(houses)
        
        # Precompute the cost of placing one mailbox for all segments
        cost = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                median = houses[(i + j) // 2]
                for l in range(i, j + 1):
                    cost[i][j] += abs(houses[l] - median)
        
        # Initialize DP array
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for m in range(1, k + 1):
                for j in range(i):
                    dp[i][m] = min(dp[i][m], dp[j][m-1] + cost[j][i-1])
        
        return dp[n][k]

Explanation: The code sorts the houses, precomputes the median cost for each segment, initializes a DP table with infinity, and iteratively fills it using previously computed results. The final answer is extracted from dp[n][k].

Go Solution

import "math"

func minDistance(houses []int, k int) int {
    n := len(houses)
    sort.Ints(houses)
    
    cost := make([][]int, n)
    for i := range cost {
        cost[i] = make([]int, n)
        for j := i; j < n; j++ {
            median := houses[(i+j)/2]
            for l := i; l <= j; l++ {
                cost[i][j] += abs(houses[l] - median)
            }
        }
    }
    
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt32
        }
    }
    dp[0][0] = 0
    
    for i := 1; i <= n; i++ {
        for m := 1; m <= k; m++ {
            for j := 0; j < i; j++ {
                if dp[j][m-1]+cost[j][i-1] < dp[i][m] {
                    dp[i][m] = dp[j][m-1] + cost[j][i-1]
                }
            }
        }
    }
    
    return dp[n][k]
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Go-specific notes: Go uses math.MaxInt32 to initialize DP values. Slices are used instead of arrays. The helper function abs handles absolute differences.

Worked Examples

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

  1. Sort houses: [1,4,8,10,20]
  2. Precompute cost array: cost[0][1] = 2, cost[1][3] = 6, cost[4][4] = 0, etc.
  3. DP filling:

  • For i=5, m=3, consider splitting at j=0..4:

  • j=0: dp[0][2] + cost[0][4]

  • j=3: dp[3][2] + cost[3][4] = 2 + 3 = 5 (minimum)

  1. Result: dp[5][3] = 5

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

  1. Sort houses: [2,3,5,12,18]
  2. Compute cost segments:
  • cost[0][2] = 4 (mailbox at 3)
  • cost[3][4] = 5 (mailbox at 15)
  1. DP finds minimum dp[5][2] = 9

Complexity Analysis

Measure Complexity Explanation
Time O(k * n^2) Precomputing cost array is O(n^2), DP table filling is O(k * n^2)
Space O(n^2) Cost array stores O(n^2) segment distances; DP array is O(n*k), dominated by cost array

The complexity is feasible because n ≤ 100 and k ≤ n.

Test Cases

# Provided examples
assert