# Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Google MicrosoftViews 614

Table of Contents

## Problem Statement

The Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution – “Find Two Non-overlapping Sub-arrays Each With Target Sum” states that you are given an integer array nums and an integer target, the task here is to find two non-overlapping subarrays from array nums such that the sum of elements of sub-array must be equal to 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.

The output must be the minimum sum of the lengths of the two required sub-arrays or return -1 if you cannot find such two sub-arrays.

### Example:

Input: nums: { 5, 2, 9, 7, 8, 2}  target : 7

Output: 3

Explanation: There are two sub-arrays ({5,2} , {7}) with target sum as 7. The length of the first array is 2 and the second array is 1. Hence output is 2+1 = 3.

## Optimized Solution

Approach: We will use a hash map with key as prefix sum (storing the sum of all array elements from 0 to i index) and value as an index (i).

• In the first loop create a hash map from the array using prefix sum and index.
• In the second loop, first, find the first sub-array from the previous index to the current index, find (current sum -target) in the map, if found update the size of the first sub-array min(size, i – m[sum-target]).
• Find the second sub-array from current index, find (sum + target) in the map, length of second sub-array will be m[sum+target] – i.
• Final result : min(res, size + min[sum+target] -i).

## Code:

### C++ Program of Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution

```class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {

unordered_map<int,int> m;
int n = arr.size();
int size = n+1;
int res = n+1;
m[0] = -1;
int sum = 0;
for(int i = 0;i < n;i++)
{
sum = sum + arr[i];
m[sum] = i;
}

sum = 0;
for (int i = 0; i < n; i++)
{
sum = sum + arr[i];
if(m.find(sum - target) != m.end())
size = min (size, i - m[sum-target]);
if(m.find(sum + target) != m.end())
res = min (res, size + m[sum+target]-i);
}

if (res == n+1)
return -1;
else
return res;
}
};```

### Java Program of Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution

```class Solution {
public int minSumOfLengths(int[] arr, int target) {

Map<Integer, Integer> m = new HashMap<>();
int n = arr.length;
int first_len = n + 1;
int total = n + 1;
m.put(0, -1);
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
m.put(sum, i);
}
sum = 0;

for (int i = 0; i < n; i++) {
sum = sum + arr[i];
if (m.containsKey(sum - target))
first_len = Math.min(first_len, i - m.get(sum - target));
if (m.containsKey(sum + target))
total = Math.min(total, first_len + m.get(sum + target) - i);
}

if (total == n+1)
return -1;
else
return total;
}
}```

## Complexity Analysis

### Time Complexity

The Time Complexity of the above code is O(n) as in this approach are traversing the array only twice in O(n) time.

### Space Complexity

The space Complexity of the above code is O(n) for the hash map to store the prefix sum.

Reference: https://en.wiktionary.org/wiki/subarray

Translate »