Leetcode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Problem Explanation:

The problem asks for finding two non-overlapping sub-arrays in a given array, where each sub-array sums up to a given target, and the sum of the lengths of these two sub-arrays is minimum. It is possible that no such pair of sub-arrays exist in the array and in that case, we return -1.

The solution takes an array of integers and a target integer as input and computes the minimum sum of the lengths of the two non-overlapping sub-arrays, if they exist, and returns -1 if they do not.

For instance, consider an array [3,2,2,4,3] and target=3. In this case, two non-overlapping sub-arrays [3] and [3] sum up to the target. Their lengths are 1 each, hence their lengths sum to 2, which is the output.

Approach:

We use an unordered map to store the cumulative sum of the array up to an index as the key and the index as the value.

We initially set the answer and the leftLength (smallest length of a sub-array from 0 to index that sums up to target) to "infinity".

We then iterate over the array, computing the cumulative sum at each index and updating the prefixToIndex map.

After that, we reset the prefix and iterate through the array again. In this iteration, we first check if there’s a sub-array from 0 to i sums up to target and if so, we update leftLength.

Next, we check if there’s a sub-array from i + 1 to j sums up to target (j will be the end of the right sub-array and the one to get from prefixToIndex[prefix + target]). If both conditions are satisfied, we've found a pair of non-overlapping sub-arrays that sum to the target and we update the answer with the minimum of the answer so far and the current pair's length sum (leftLength + it->second - i).

In the end, if the answer is still "infinity", we return -1, else we return the answer.

Python Solution:

You are free to write explanation in code comments like following:

1
2python
3class Solution:
4    def minSumOfLengths(self, arr: List[int], target: int) -> int:
5        prefix_to_index = {0: -1}
6        length, cum_sum = [float("inf")]*(len(arr)+1), 0
7        ans = float("inf")
8
9        for i in range(len(arr)):
10            cum_sum += arr[i]
11            if cum_sum-target in prefix_to_index:
12                length[i] = min(length[i], i - prefix_to_index[cum_sum-target])
13            if i > 0:
14                length[i] = min(length[i], length[i-1])
15            prev = prefix_to_index.get(cum_sum+target, None)
16            if prev is not None and length[prev] < float("inf"):
17                ans = min(ans, length[prev] + i - prev)
18            prefix_to_index[cum_sum] = i
19
20        return -1 if ans == float("inf") else ans

Java Solution:

1
2java
3class Solution {
4    public int minSumOfLengths(int[] arr, int target) {
5        int n = arr.length;
6        int ans = Integer.MAX_VALUE;
7        int leftLength = Integer.MAX_VALUE;
8        HashMap<Integer, Integer> prefixToIndex = new HashMap<>();
9        prefixToIndex.put(0, -1);
10        
11        int prefix = 0;
12        for (int i = 0; i < n; i++) {
13            prefix += arr[i];
14            prefixToIndex.put(prefix, i);
15        }
16
17        prefix = 0;
18        for (int i = 0; i < n; i++) {
19            prefix += arr[i];
20            if (prefixToIndex.containsKey(prefix - target))
21                leftLength = Math.min(leftLength, i - prefixToIndex.get(prefix - target));
22            if (leftLength < Integer.MAX_VALUE && prefixToIndex.containsKey(prefix + target))
23                ans = Math.min(ans, leftLength + prefixToIndex.get(prefix + target) - i);
24        }
25
26        return ans == Integer.MAX_VALUE ? -1 : ans;
27    }
28}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int minSumOfLengths(vector<int>& arr, int target) {
6        int n = arr.size(), res = INT_MAX, sum = 0;
7        unordered_map<int, int> m;
8        m[0] = -1;
9        vector<int> dp(n, INT_MAX);
10        for (int i = 0; i < n; ++i) {
11            sum += arr[i];
12            if (m.count(sum - target))
13                dp[i] = min(i - m[sum - target], i > 0 ? dp[i - 1] : INT_MAX);
14            else if (i > 0)
15                dp[i] = dp[i - 1];
16            if (i > 0 && m.count(sum - target) && dp[m[sum - target]] != INT_MAX)
17                res = min(res, dp[m[sum - target]] + i - m[sum - target]);
18            m[sum] = i;
19        }
20        return res == INT_MAX ? -1 : res;
21    }
22};

JavaScript Solution:

1
2javascript
3var minSumOfLengths = function(arr, target) {
4    let preSum = new Map()
5    preSum.set(0, -1)
6    let dp = new Array(arr.length).fill(Number.MAX_SAFE_INTEGER)
7    let sum = 0
8    let ans = Number.MAX_SAFE_INTEGER
9    for(let i = 0; i < arr.length; i++){
10        sum += arr[i]
11        if(preSum.has(sum - target)){
12            if(preSum.get(sum - target) !== -1){
13                let past = preSum.get(sum - target)
14                if(past >= 0){
15                    ans = Math.min(ans, dp[past] + i - past)
16                }
17            }
18        }
19        dp[i] = Math.min((sum === target ? i + 1 : Number.MAX_SAFE_INTEGER), i > 0 ? dp[i - 1] : Number.MAX_SAFE_INTEGER)
20        preSum.set(sum, i)
21    }
22    return ans == Number.MAX_SAFE_INTEGER ? -1 : ans
23};

C# Solution:

1
2Csharp
3public class Solution {
4    public int MinSumOfLengths(int[] arr, int target) {
5        int n = arr.Length;
6        var prefix = new Dictionary<int, int>() { [0] = -1 };
7        int sum = 0, left_len = n + 1, res = n + 1;
8        var dp = new int[n];
9        Array.Fill(dp, n + 1);
10        for(int i = 0; i < n; ++i) {
11            sum += arr[i];
12            if (prefix.ContainsKey(sum - target)) {
13                left_len = Math.Min(left_len, i - prefix[sum - target]);
14                dp[i] = (sum == target) ? i + 1 : left_len;
15            } else {
16                dp[i] = sum == target ? i + 1 : (i > 0 ? dp[i - 1] : n + 1);
17            }
18            res = Math.Min(res, (i - dp[i] >= 0 ? dp[i - dp[i]] : n + 1) + dp[i]);
19            prefix[sum] = i;
20        }
21        return res <= n ? res :  -1;
22    }
23}

Both solutions take advantage of the programming concept of dynamic programming and sliding window. The solutions have linear time complexity (O(n)) because we iterate through the array only once, where n is the size of the input array. The space complexity is also linear (O(n)), where n is again the size of the input array, since we store the cumulative sum and the smallest lengths for every index in separate arrays.### Ruby Solution:

1
2ruby
3def min_sum_of_lengths(arr, target)
4  prefix_to_index = {0=>-1}
5  len, cum_sum = Array.new(arr.length+1, Float::INFINITY), 0
6  ans = Float::INFINITY
7
8  arr.each_with_index do |val, i|
9    cum_sum += val
10    if prefix_to_index.key?(cum_sum-target)
11      len[i] = [len[i], i - prefix_to_index[cum_sum-target]].min
12    end
13    len[i] = [len[i-1], len[i]].min if i > 0
14    if prefix_to_index.key?(cum_sum+target) && len[prefix_to_index[cum_sum+target]] < Float::INFINITY
15      ans = [ans, len[prefix_to_index[cum_sum+target]] + i - prefix_to_index[cum_sum+target]].min
16    end
17    prefix_to_index[cum_sum] = i
18  end
19
20  ans == Float::INFINITY ? -1 : ans
21end

Swift Solution:

1
2swift
3func minSumOfLengths(_ arr: [Int], _ target: Int) -> Int {
4    var prefixToIndex: [Int: Int] = [0: -1]
5    var length = [Int](repeating: Int.max, count: arr.count + 1), cumSum = 0, res = Int.max
6
7    for i in 0..<arr.count {
8        cumSum += arr[i]
9        if let startIndex = prefixToIndex[cumSum - target] {
10            length[i] = min(length[i], i - startIndex)
11        }
12        
13        if i > 0 { length[i] = min(length[i], length[i - 1]) }
14        
15        if let index = prefixToIndex[cumSum + target], length[index] < Int.max {
16            res = min(res, length[index] + i - index)
17        }
18        
19        prefixToIndex[cumSum] = i
20    }
21    
22    return res == Int.max ? -1 : res
23}

Julia Solution:

1
2julia
3function minSumOfLengths(arr, target)
4    prefix_to_index = Dict(0 => -1)
5    len, cum_sum = fill(Inf, length(arr) + 1), 0
6    ans = Inf
7
8    for (i, val) in enumerate(arr)
9        cum_sum += val
10        if haskey(prefix_to_index, cum_sum - target)
11            len[i] = min(len[i], i - prefix_to_index[cum_sum - target] - 1)
12        end
13
14        len[i] = min(len[i - 1], len[i]) if i > 1
15
16        if haskey(prefix_to_index, cum_sum + target)
17            ans = min(ans, len[prefix_to_index[cum_sum + target]] + i - prefix_to_index[cum_sum + target])
18        end
19
20        prefix_to_index[cum_sum] = i
21    end
22
23    return ans == Inf ? -1 : ans
24end

Wrapping up, choosing which solution to implement depends on the language you're using—like whether you want something straightforward in Python, or you want more type safety in a language like Java—and how comfortable you are with dealing with data structures such as dictionaries and arrays. While this problem is not trivial, breaking it down into smaller subproblems and tackling each one will make the problem solvable. Each solution we discussed in this article takes advantage of the programming concepts of dynamic programming and sliding window to solve the problem efficiently.