Add solution #1478

JoshCrozier · JoshCrozier · commit 4a42a2cc43fe · 2025-04-15T23:16:25.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,322 LeetCode solutions in JavaScript
+# 1,323 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1130,6 +1130,7 @@
 1475|[Final Prices With a Special Discount in a Shop](./solutions/1475-final-prices-with-a-special-discount-in-a-shop.js)|Easy|
 1476|[Subrectangle Queries](./solutions/1476-subrectangle-queries.js)|Medium|
 1477|[Find Two Non-overlapping Sub-arrays Each With Target Sum](./solutions/1477-find-two-non-overlapping-sub-arrays-each-with-target-sum.js)|Medium|
+1478|[Allocate Mailboxes](./solutions/1478-allocate-mailboxes.js)|Hard|
 1480|[Running Sum of 1d Array](./solutions/1480-running-sum-of-1d-array.js)|Easy|
 1481|[Least Number of Unique Integers after K Removals](./solutions/1481-least-number-of-unique-integers-after-k-removals.js)|Medium|
 1486|[XOR Operation in an Array](./solutions/1486-xor-operation-in-an-array.js)|Easy|
diff --git a/solutions/1478-allocate-mailboxes.js b/solutions/1478-allocate-mailboxes.js
@@ -0,0 +1,51 @@
+/**
+ * 1478. Allocate Mailboxes
+ * https://leetcode.com/problems/allocate-mailboxes/
+ * Difficulty: Hard
+ *
+ * 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.
+ */
+
+/**
+ * @param {number[]} houses
+ * @param {number} k
+ * @return {number}
+ */
+var minDistance = function(houses, k) {
+  houses.sort((a, b) => a - b);
+  const n = houses.length;
+  const cache = new Map();
+
+  return findMinDistance(0, k);
+
+  function medianDistance(start, end) {
+    let sum = 0;
+    const mid = Math.floor((start + end) / 2);
+    for (let i = start; i <= end; i++) {
+      sum += Math.abs(houses[i] - houses[mid]);
+    }
+    return sum;
+  }
+
+  function findMinDistance(index, mailboxes) {
+    if (index === n) return mailboxes === 0 ? 0 : Infinity;
+    if (mailboxes === 0) return Infinity;
+
+    const key = `${index}:${mailboxes}`;
+    if (cache.has(key)) return cache.get(key);
+
+    let minDist = Infinity;
+    for (let j = index; j < n && n - j >= mailboxes; j++) {
+      const distance = medianDistance(index, j) + findMinDistance(j + 1, mailboxes - 1);
+      minDist = Math.min(minDist, distance);
+    }
+
+    cache.set(key, minDist);
+    return minDist;
+  }
+};
