Code Implementation

from functools import lru_cache

class Solution:
    def minDistance(self, houses, k):
        houses.sort()
        n = len(houses)
        
        # Precompute cost[i][j]: min total distance to cover houses[i:j+1] with 1 mailbox
        cost = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                mid = (i + j) // 2
                for x in range(i, j+1):
                    cost[i][j] += abs(houses[x] - houses[mid])

        @lru_cache(None)
        def dp(i, k):
            if k == 0 and i == n:
                return 0
            if k == 0 or i == n:
                return float('inf')
            res = float('inf')
            for j in range(i, n):
                res = min(res, cost[i][j] + dp(j+1, k-1))
            return res

        return dp(0, k)
      

class Solution {
public:
    int minDistance(vector<int>& houses, int k) {
        sort(houses.begin(), houses.end());
        int n = houses.size();
        vector<vector<int>> cost(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                int mid = (i + j) / 2;
                for (int x = i; x <= j; ++x)
                    cost[i][j] += abs(houses[x] - houses[mid]);
            }
        }
        vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX/2));
        dp[n][0] = 0;
        for (int i = n-1; i >= 0; --i) {
            for (int m = 1; m <= k; ++m) {
                for (int j = i; j < n; ++j) {
                    if (dp[j+1][m-1] != INT_MAX/2)
                        dp[i][m] = min(dp[i][m], cost[i][j] + dp[j+1][m-1]);
                }
            }
        }
        return dp[0][k];
    }
};
      

class Solution {
    public int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        int n = houses.length;
        int[][] cost = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                int mid = (i + j) / 2;
                for (int x = i; x <= j; ++x)
                    cost[i][j] += Math.abs(houses[x] - houses[mid]);
            }
        }
        int[][] dp = new int[n+1][k+1];
        for (int i = 0; i <= n; ++i)
            Arrays.fill(dp[i], Integer.MAX_VALUE/2);
        dp[n][0] = 0;
        for (int i = n-1; i >= 0; --i) {
            for (int m = 1; m <= k; ++m) {
                for (int j = i; j < n; ++j) {
                    dp[i][m] = Math.min(dp[i][m], cost[i][j] + dp[j+1][m-1]);
                }
            }
        }
        return dp[0][k];
    }
}
      

var minDistance = function(houses, k) {
    houses.sort((a, b) => a - b);
    let n = houses.length;
    let cost = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = 0; i < n; ++i) {
        for (let j = i; j < n; ++j) {
            let mid = Math.floor((i + j) / 2);
            for (let x = i; x <= j; ++x)
                cost[i][j] += Math.abs(houses[x] - houses[mid]);
        }
    }
    let dp = Array.from({length: n+1}, () => Array(k+1).fill(Infinity));
    dp[n][0] = 0;
    for (let i = n-1; i >= 0; --i) {
        for (let m = 1; m <= k; ++m) {
            for (let j = i; j < n; ++j) {
                dp[i][m] = Math.min(dp[i][m], cost[i][j] + dp[j+1][m-1]);
            }
        }
    }
    return dp[0][k];
};
      

Problem Description

Given an array houses representing the locations of houses along a street (as integers), and an integer k representing the number of mailboxes to allocate, the goal is to minimize the total distance between each house and its nearest mailbox. You must place exactly k mailboxes at integer positions (not necessarily at house positions), and each house is assigned to its closest mailbox. The total distance is the sum of the distances from each house to its assigned mailbox.

• You must allocate exactly k mailboxes.
• Each house must be assigned to one mailbox.
• Mailboxes may be placed at any integer position, but optimal placement is typically at house positions.
• The answer is the minimum possible total distance.
• Each house location is unique.

Thought Process

At first glance, the problem appears to require trying all possible ways to assign houses to mailboxes and all possible mailbox locations, which would be computationally expensive. The brute-force approach would consider every way to split the houses into k groups and place a mailbox for each group, calculating the total distance for each possibility.

However, we can observe that for any group of houses, the optimal mailbox location is at the median house position, as this minimizes the sum of absolute differences (the total walking distance). Thus, the challenge reduces to partitioning the sorted list of houses into k contiguous groups, and for each group, placing a mailbox at the median and summing the costs.

This insight leads to a dynamic programming (DP) approach, where we recursively try all ways to split the houses into k groups and use memoization to avoid redundant calculations.

Solution Approach

Let's break down the algorithm step-by-step:

1. Sort the Houses: Since grouping is easier on sorted data, first sort the houses array.
2. Precompute Cost for Each Interval: For every pair (i, j), precompute the minimal total distance to cover houses[i]...houses[j] with one mailbox. This is done by placing the mailbox at the median house position for that interval.
3. Dynamic Programming:
   • Define dp(i, k) as the minimum total distance to allocate k mailboxes starting from house i.
   • For each position j from i to n-1, compute the cost for houses i to j as one group, and recursively solve for the remaining houses and mailboxes.
   • Memoize the results to avoid recomputation.
4. Base Cases:
   • If there are no houses left and no mailboxes left, cost is 0.
   • If either houses or mailboxes run out before the other, the result is infinity (invalid split).
5. Return the Answer: Start the DP from i = 0 and k mailboxes.

This approach efficiently explores all valid groupings and leverages the optimal property of medians for minimizing distances.

Example Walkthrough

Let's consider the input houses = [1, 4, 8, 10, 20] and k = 3.

1. Sort the houses: Already sorted: [1, 4, 8, 10, 20].
2. Precompute cost:
   • For houses [1]: cost = 0 (only one house)
   • For houses [1, 4]: median is 1 or 4, cost = |1-1| + |4-1| = 3
   • For houses [1, 4, 8]: median is 4, cost = |1-4| + |4-4| + |8-4| = 3 + 0 + 4 = 7
   • ...and so on for all intervals.
3. DP Splitting:
   • Try splitting after the first house, after the second, etc., and recursively solve for the rest.
   • For example, first mailbox covers [1] (cost 0), then solve for [4,8,10,20] with 2 mailboxes.
   • Or, first mailbox covers [1,4] (cost 3), then solve for [8,10,20] with 2 mailboxes, etc.
   • Choose the split with the minimal total cost.
4. Result: The minimum total distance is 5:
   • Mailboxes at 1, 8, 20 (covering [1,4], [8,10], [20])
   • Distances: |1-1|+|4-1| = 3, |8-8|+|10-8| = 2, |20-20| = 0, total = 3+2+0 = 5

Time and Space Complexity

• Brute-force: Trying all partitions is exponential in the number of houses and mailboxes, leading to impractical runtimes for large inputs.
• Optimized DP Approach:
  • There are O(n²) intervals for precomputing costs.
  • The DP table has O(nk) entries, and each entry may iterate up to O(n) splits, so total time is O(n³k).
  • Space is O(n²) for cost table and O(nk) for DP table.
• In practice, with optimizations and memoization, this is efficient enough for typical Leetcode constraints.

Summary

The "Allocate Mailboxes" problem leverages the property that the median minimizes the sum of absolute distances in a group. By precomputing costs for all intervals and using dynamic programming to optimally split the houses into k groups, we can efficiently find the minimal total distance. The solution elegantly transforms a seemingly combinatorial problem into a manageable DP by exploiting mathematical and structural properties of the problem.