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

In this guide, you will get 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution with the best time and space complexity. The solution to Find Two Non-overlapping Sub-arrays Each With Target Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find Two Non-overlapping Sub-arrays Each With Target Sum solution in C++
4. Find Two Non-overlapping Sub-arrays Each With Target Sum solution in Java
5. Find Two Non-overlapping Sub-arrays Each With Target Sum solution in Python
6. Additional Resources

Problem Statement of Find Two Non-overlapping Sub-arrays Each With Target Sum

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution in C++

class Solution {
 public:
  int minSumOfLengths(vector<int>& arr, int target) {
    int ans = INT_MAX;
    int leftLength = INT_MAX;
    int prefix = 0;
    unordered_map<int, int> prefixToIndex{{0, -1}};

    for (int i = 0; i < arr.size(); ++i) {
      prefix += arr[i];
      prefixToIndex[prefix] = i;
    }

    prefix = 0;

    for (int i = 0; i < arr.size(); ++i) {
      prefix += arr[i];
      if (const auto it = prefixToIndex.find(prefix - target);
          it != prefixToIndex.cend())
        leftLength = min(leftLength, i - it->second);
      if (leftLength < INT_MAX)
        if (const auto it = prefixToIndex.find(prefix + target);
            it != prefixToIndex.cend())
          ans = min(ans, leftLength + it->second - i);
    }

    return ans == INT_MAX ? -1 : ans;
  }
};
/* code provided by PROGIEZ */

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution in Java

class Solution {
  public int minSumOfLengths(int[] arr, int target) {
    int ans = Integer.MAX_VALUE;
    int leftLength = Integer.MAX_VALUE;
    int prefix = 0;
    Map<Integer, Integer> prefixToIndex = new HashMap<>();
    prefixToIndex.put(0, -1);

    for (int i = 0; i < arr.length; ++i) {
      prefix += arr[i];
      prefixToIndex.put(prefix, i);
    }

    prefix = 0;

    for (int i = 0; i < arr.length; ++i) {
      prefix += arr[i];
      if (prefixToIndex.containsKey(prefix - target))
        leftLength = Math.min(leftLength, i - prefixToIndex.get(prefix - target));
      if (leftLength < Integer.MAX_VALUE)
        if (prefixToIndex.containsKey(prefix + target))
          ans = Math.min(ans, leftLength + prefixToIndex.get(prefix + target) - i);
    }

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}
// code provided by PROGIEZ

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode Solution in Python

class Solution {
 public:
  int minSumOfLengths(vector<int>& arr, int target) {
    int ans = INT_MAX;
    int sum = 0;  // the window sum
    // best[i] := the minimum length of subarrays in arr[0..i] that have
    // sum = target
    vector<int> best(arr.size(), INT_MAX);

    for (int l = 0, r = 0; r < arr.size(); ++r) {
      sum += arr[r];  // Expand the window.
      while (sum > target)
        sum -= arr[l++];  // Shrink the window.
      if (sum == target) {
        if (l > 0 && best[l - 1] != INT_MAX)
          ans = min(ans, best[l - 1] + r - l + 1);
        best[r] = min(best[r], r - l + 1);
      }
      if (r > 0)
        best[r] = min(best[r], best[r - 1]);
    }

    return ans == INT_MAX ? -1 : ans;
  }
};
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.