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

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