We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Allocate Mailboxes

Number: 1571

Difficulty: Hard

Paid? No

Companies: Amazon, Bloomberg

Problem Description

Given a sorted list of house positions and an integer k, allocate k mailboxes along the street such that the total distance from each house to its nearest mailbox is minimized. Return this minimum total distance.

Key Insights

  • Sorting the houses simplifies the distance computation.
  • For any contiguous subset of houses, placing a mailbox at the median minimizes sum of distances.
  • Precompute cost for serving houses i to j with one mailbox using the median.
  • Use dynamic programming where dp[i][k] represents the minimum cost to allocate k mailboxes for the first i houses.
  • Transition: dp[i][k] is the minimum over all possible partitions into dp[j][k-1] plus cost for houses j+1 to i.

Space and Time Complexity

Time Complexity: O(n^2 * k) where n is the number of houses (n <= 100). Space Complexity: O(n^2 + n*k) used for the cost precomputation and DP table.

Solution

We start by sorting the house positions. For every possible interval [i, j], we precompute the cost to cover all houses in that interval with a single mailbox placed at the median position. This cost can be computed by summing the absolute differences with the median value.

Next, we define a DP array where dp[i][m] (or dp[i][k]) denotes the minimum cost to cover the first i houses with m mailboxes. For dp[i][m], we examine all possible previous partitions (dp[j][m-1] for 0 <= j < i) and add the precomputed cost for covering houses j+1 to i with one mailbox.

Finally, the answer is dp[n][k] with n denoting the total number of houses. The main challenges include correctly precomputing the costs and setting up the DP transitions, with careful handling of base cases.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def minDistance(self, houses, k):
        # Sort houses to ensure contiguous intervals
        houses.sort()
        n = len(houses)
        # Precompute the cost for a single mailbox for all intervals [i, j]
        cost = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                # Use median position for the interval [i, j]
                median = houses[(i + j) // 2]
                # Calculate total distance from each house to the median
                for t in range(i, j + 1):
                    cost[i][j] += abs(houses[t] - median)
        
        # Initialize dp array, dp[i][m] is min cost for first i houses with m mailboxes.
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0  # No houses and 0 mailboxes requires 0 cost
        
        # Fill dp table
        for i in range(1, n + 1):  # i houses considered
            for m in range(1, k + 1):  # using m mailboxes
                # Try partitioning houses from 0 to i-1
                for j in range(i):
                    # Update dp[i][m] with best partition ending at house index i-1 from index j
                    dp[i][m] = min(dp[i][m], dp[j][m - 1] + cost[j][i - 1])
        
        # Minimum cost to cover all houses with k mailboxes
        return dp[n][k]


# Example usage:
# sol = Solution()
# print(sol.minDistance([1,4,8,10,20], 3))  # Expected output: 5
← Back to All Questions