1478. Allocate Mailboxes

Description

Given the array houses where houses[i] is the location of the ith house along a street and an integer k, allocate k mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 

Example 2:

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

 

Constraints:

• 1 <= k <= houses.length <= 100
• 1 <= houses[i] <= 104
• All the integers of houses are unique.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n³+n²k -> n³)
• Space complexity: O(n²+nk -> n²)

 

JavaScript

/**
 * @param {number[]} houses
 * @param {number} k
 * @return {number}
 */
const minDistance = function (houses, k) {
  const n = houses.length;
  const cost = Array.from({ length: n }, () => new Array(n).fill(0));
  const dp = Array.from({ length: n }, () => new Array(k + 1).fill(-1));

  houses.sort((a, b) => a - b);

  for (let a = 0; a < n; a++) {
    for (let b = a + 1; b < n; b++) {
      const median = Math.floor((a + b) / 2);

      for (let index = a; index <= b; index++) {
        cost[a][b] += Math.abs(houses[index] - houses[median]);
      }
    }
  }

  const allocateMailbox = (start, mailbox) => {
    if (start >= n && mailbox === k) return 0;
    if (start >= n || mailbox === k) return Number.MAX_SAFE_INTEGER;
    if (dp[start][mailbox] !== -1) return dp[start][mailbox];
    let result = Number.MAX_SAFE_INTEGER;

    for (let index = start; index < n; index++) {
      const currentCost = cost[start][index];
      const nextCost = allocateMailbox(index + 1, mailbox + 1);

      result = Math.min(currentCost + nextCost, result);
    }

    dp[start][mailbox] = result;

    return result;
  };

  return allocateMailbox(0, 0);
};