1478. Allocate Mailboxes - Detailed Explanation

Problem Statement

Description

Given an array houses where houses[i] is the position of the ith house on a number line, and an integer k, you want to build k mailboxes at integer locations. Return the minimum total distance between each house and its nearest mailbox.

Examples

Example 1

Input: houses = [1,4,8,10,20], k = 3  
Output: 5  
Explanation: Sort houses → [1,4,8,10,20].  
Place mailboxes at 3, 9, 20.  
Distances: |1-3|+|4-3| + |8-9|+|10-9| + |20-20| = 2+1 + 1+1 + 0 = 5  

Example 2

Input: houses = [2,3,5,12,18], k = 2  
Output: 9  
Explanation: Sort → [2,3,5,12,18].  
Split into [2,3,5] and [12,18].  
Best mailbox positions are at medians 3 and 12.  
Distances: (|2-3|+|3-3|+|5-3|)=1+0+2=3 plus (|12-12|+|18-12|)=0+6=6 → total 9  

Example 3

Input: houses = [7,4,6,1], k = 1  
Output: 8  
Explanation: Sort → [1,4,6,7]. One mailbox at median index (1+4+6+7)/2→between 4 and 6, either 4 or 6 → pick 6.  
Distances: |1-6|+|4-6|+|6-6|+|7-6| = 5+2+0+1 = 8  

Constraints

• 1 ≤ houses.length ≤ 100
• 1 ≤ houses[i] ≤ 10⁴
• All houses[i] are distinct
• 1 ≤ k ≤ houses.length

Hints

1. Why sort houses before anything else? How does that help grouping?
2. For any contiguous group of houses, where’s the best mailbox location? How can you compute that cost quickly for every possible interval?

Brute‑Force Partitioning Approach

Idea

Try every way to split the sorted houses into k contiguous groups, place one mailbox per group at its median, and sum distances.

Steps

1. Sort houses.
2. Define a recursive function dfs(start, rem) that returns the minimum cost to cover houses[start:] with rem mailboxes.
3. If rem == 1, cost = distance‐sum when placing at median of houses[start:].
4. Otherwise, for every end from start to n - rem, consider one mailbox covering start…end, then recurse on end+1 with rem-1.
5. Take the minimum over all splits.

Why It’s Impractical

• There are O(nᵏ) ways to choose splits. With n up to 100, k up to n, this explodes exponentially.

Optimized DP with Precomputed Costs

Idea

1. Precompute cost[i][j] = minimal distance if one mailbox serves houses[i…j]. This is placing the mailbox at the median index m = (i+j)//2.
2. Use DP: dp[g][i] = min total distance serving the first i+1 houses with g mailboxes.
3. Recurrence:

   dp[1][i] = cost[0][i]
   dp[g][i] = min for all t < i of (dp[g-1][t] + cost[t+1][i])
   

Steps

1. Sort houses; let n = len(houses).
2. Build cost array of size n×n:
   • For each i ≤ j, compute median index m = (i+j)//2 and sum abs(houses[x] - houses[m]) for x in [i…j].
3. Initialize a DP table dp[k+1][n] with ∞.
4. Set dp[1][i] = cost[0][i] for all i.
5. For g from 2 to k, for i from g-1 to n-1:
   • For t from g-2 to i-1:

     dp[g][i] = min(dp[g][i], dp[g-1][t] + cost[t+1][i])
     

6. Answer = dp[k][n-1].

Complexity Analysis

• Sorting: O(n log n)
• Cost Precompute: O(n²) intervals × O(n) summation → O(n³), but you can optimize each interval in O(1) amortized by two‐pointer median expansion; still O(n²) overall for n≤100.
• DP: O(k × n²)
• Total: O(k n² + n² + n log n) → dominated by O(k n²), feasible for n≤100, k≤100.

Code (Python)