Practice/Amazon/Leetcode 1478. Allocate Mailboxes

Leetcode 1478. Allocate Mailboxes

CodingMust

Problem

You are tasked with placing k distribution centers along a straight road to serve a set of houses. Each house is located at a specific position on this road, and each house will receive deliveries from the nearest distribution center.

Your goal is to determine the optimal positions for the k distribution centers such that the total distance from all houses to their respective nearest centers is minimized.

Return the minimum possible sum of distances.

Requirements

1. Choose k positions to place distribution centers on the road
2. Each house must be served by its nearest distribution center
3. Minimize the total sum of distances from all houses to their nearest centers
4. Centers can be placed at any position on the road (not necessarily at house locations)

Constraints

• 1 ≤ k ≤ houses.length ≤ 100
• 1 ≤ houses[i] ≤ 10,000
• All house positions are unique
• Expected time complexity: O(n³) or better
• Expected space complexity: O(n²)

Examples

Example 1:

Input: houses = [1, 4, 8], k = 1 Output: 7 Explanation: With only one center, place it at position 4 (the median). Distances: |1-4| + |4-4| + |8-4| = 3 + 0 + 4 = 7

Example 2:

Input: houses = [2, 3, 5, 12], k = 2 Output: 5 Explanation: Place centers to serve groups [2,3,5] and [12]. The first center goes at position 3 (median of [2,3,5]). The second center goes at position 12 (median of [12]). Total distance: (1 + 0 + 2) + 0 = 5

Example 3:

Input: houses = [7, 4, 6, 1], k = 4 Output: 0 Explanation: Place one center at each house. All distances are 0.