Find Two Non Overlapping Sub Arrays Each With Target Sum - Leetcode Solution

Problem Statement:

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find one where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of two such sub-arrays. If there's no such sub-array, return -1.

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 (index 0 and 3) sub-arrays as they have the minimum sum of lengths.

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.

Solution:

To solve the problem, we use a map to store the last index at which target sum occurs. We also use two pointers to traverse the array:

• left: The index from where we will start a subarray.
• right: The index up to where we will be scanning the subarray.

We calculate the prefix sum of the array which is the sum of all elements to the left of each index i. Then we use the below logic to find the two non-overlapping subarrays each with a target sum:

• We start with our left and right pointers pointing to the start of the array and a variable minimum which stores the length of the two non-overlapping sub-arrays.
• We calculate the sum of the subarray arr[left, right].
• If sum is less than the target, we increment right and calculate the new sum.
• If the sum is greater than the target, we increment left and calculate the new sum.
• If the sum of the subarray arr[left, right] is equal to the target, we check if we have already seen a subarray left of this subarray that also has a target sum. If we have, then this subarray will form a new non-overlapping pair with that one. We update the minimum accordingly.
• We store the last index at which the target sum occurs in our map with the key as the prefix sum before the start of the subarray and the value as the end index of the subarray.
• We update the minimum sum accordingly.

The code for the same is given below:

class Solution { public: int minSumOfLengths(vector<int>& arr, int target) { int n = arr.size(); unordered_map<int, int> mp{{0, -1}}; vector<int> dp(n, INT_MAX); int left = 0, sum = 0, res = INT_MAX; for (int right = 0; right < n; ++right) { sum += arr[right]; while (sum > target) { sum -= arr[left++]; } if (sum == target) { if (mp.count(left - 1)) { int len = right - left + 1; res = min(res, len + dp[mp[left - 1]]); } dp[right] = right > 0 ? dp[right - 1] : INT_MAX; dp[right] = min(dp[right], right - left + 1); mp[sum + (left > 0) * arr[left - 1]] = right; } else { dp[right] = right > 0 ? dp[right - 1] : INT_MAX; } } return res == INT_MAX ? -1 : res; } };

Time Complexity: O(n)

Space Complexity: O(n)

1