LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

 

Constraints:

• 1 <= arr.length <= 105
• 1 <= arr[i] <= 1000
• 1 <= target <= 108

Solutions

Solution 1: Hash Table + Prefix Sum + Dynamic Programming

We can use a hash table d to record the most recent position where each prefix sum appears, with the initial value d[0]=0.

Define f[i] as the minimum length of a subarray with sum equal to target among the first i elements. Initially, f[0]=∞.

Iterate through the array arr. For the current position i, calculate the prefix sum s. If s - target exists in the hash table, let j = d[s - target], then f[i] = min(f[i], i - j), and the answer is ans = min(ans, f[j] + i - j). Continue to the next position.

Finally, if the answer is greater than the array length, return -1; otherwise, return the answer.

The complexity is O(n), and the space complexity is O(n), where n is the length of the array.

PythonJavaC++GoTypeScript

class Solution: def minSumOfLengths(self, arr: List[int], target: int) -> int: d = {0: 0} s, n = 0, len(arr) f = [inf] * (n + 1) ans = inf for i, v in enumerate(arr, 1): s += v f[i] = f[i - 1] if s - target in d: j = d[s - target] f[i] = min(f[i], i - j) ans = min(ans, f[j] + i - j) d[s] = i return -1 if ans > n else ans(code-box)

class Solution { public int minSumOfLengths(int[] arr, int target) { Map<Integer, Integer> d = new HashMap<>(); d.put(0, 0); int n = arr.length; int[] f = new int[n + 1]; final int inf = 1 << 30; f[0] = inf; int s = 0, ans = inf; for (int i = 1; i <= n; ++i) { int v = arr[i - 1]; s += v; f[i] = f[i - 1]; if (d.containsKey(s - target)) { int j = d.get(s - target); f[i] = Math.min(f[i], i - j); ans = Math.min(ans, f[j] + i - j); } d.put(s, i); } return ans > n ? -1 : ans; } }(code-box)

class Solution { public: int minSumOfLengths(vector<int>& arr, int target) { unordered_map<int, int> d; d[0] = 0; int s = 0, n = arr.size(); int f[n + 1]; const int inf = 1 << 30; f[0] = inf; int ans = inf; for (int i = 1; i <= n; ++i) { int v = arr[i - 1]; s += v; f[i] = f[i - 1]; if (d.count(s - target)) { int j = d[s - target]; f[i] = min(f[i], i - j); ans = min(ans, f[j] + i - j); } d[s] = i; } return ans > n ? -1 : ans; } };(code-box)

func minSumOfLengths(arr []int, target int) int { d := map[int]int{0: 0} const inf = 1 << 30 s, n := 0, len(arr) f := make([]int, n+1) f[0] = inf ans := inf for i, v := range arr { i++ f[i] = f[i-1] s += v if j, ok := d[s-target]; ok { f[i] = min(f[i], i-j) ans = min(ans, f[j]+i-j) } d[s] = i } if ans > n { return -1 } return ans }(code-box)

function minSumOfLengths(arr: number[], target: number): number { const d = new Map<number, number>(); d.set(0, 0); let s = 0; const n = arr.length; const f: number[] = Array(n + 1); const inf = 1 << 30; f[0] = inf; let ans = inf; for (let i = 1; i <= n; ++i) { const v = arr[i - 1]; s += v; f[i] = f[i - 1]; if (d.has(s - target)) { const j = d.get(s - target)!; f[i] = Math.min(f[i], i - j); ans = Math.min(ans, f[j] + i - j); } d.set(s, i); } return ans > n ? -1 : ans; }(code-box)