Add solution #1477

JoshCrozier · JoshCrozier · commit 7b92cb4c7351 · 2025-04-15T23:11:42.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,321 LeetCode solutions in JavaScript
+# 1,322 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1129,6 +1129,7 @@
 1473|[Paint House III](./solutions/1473-paint-house-iii.js)|Hard|
 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|
 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/1477-find-two-non-overlapping-sub-arrays-each-with-target-sum.js b/solutions/1477-find-two-non-overlapping-sub-arrays-each-with-target-sum.js
@@ -0,0 +1,43 @@
+/**
+ * 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
+ * https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/
+ * Difficulty: Medium
+ *
+ * You are given an array of integers arr and an integer target.
+ *
+ * You have to find two non-overlapping sub-arrays of arr each with a sum equal target. There
+ * can be multiple answers so you have to find an answer where the sum of the lengths of the
+ * two sub-arrays is minimum.
+ *
+ * Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you
+ * cannot find such two sub-arrays.
+ */
+
+/**
+ * @param {number[]} arr
+ * @param {number} target
+ * @return {number}
+ */
+var minSumOfLengths = function(arr, target) {
+  const prefixSums = new Map([[0, -1]]);
+  let currentSum = 0;
+  let minLength = Infinity;
+  const minLengths = new Array(arr.length).fill(Infinity);
+  let result = Infinity;
+
+  for (let i = 0; i < arr.length; i++) {
+    currentSum += arr[i];
+    if (prefixSums.has(currentSum - target)) {
+      const start = prefixSums.get(currentSum - target);
+      const length = i - start;
+      minLength = Math.min(minLength, length);
+      if (start >= 0 && minLengths[start] !== Infinity) {
+        result = Math.min(result, length + minLengths[start]);
+      }
+    }
+    minLengths[i] = minLength;
+    prefixSums.set(currentSum, i);
+  }
+
+  return result === Infinity ? -1 : result;
+};
