Scale Engineer

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

Med
#1364Time: O(N + k^2), where N is the length of the array and k is the number of sub-arrays with the target sum. The first step (finding sub-arrays) is O(N). The second step (pairing them) is O(k^2). In the worst case, k can be O(N), making the total complexity O(N^2).Space: O(k), where k is the number of sub-arrays with the target sum. In the worst case, k can be O(N), leading to O(N) space complexity.
Patterns
Sliding WindowDynamic Programming
Algorithms
Binary Search
Data structures
ArrayHash Table

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach first identifies all possible sub-arrays that sum up to the target. Then, it iterates through all possible pairs of these sub-arrays to find a non-overlapping pair with the minimum sum of lengths.

Algorithm

  • Step 1: Find all target-sum sub-arrays.
    • Create a list, validSubarrays, to store information (start index, end index) about sub-arrays that sum to target.
    • Use a sliding window approach to iterate through the input array arr once. This is an efficient way to find all such sub-arrays in O(N) time since all numbers are positive.
    • For each sub-array found, add its start and end indices to the validSubarrays list.
  • Step 2: Check all pairs of sub-arrays.
    • If the number of sub-arrays in validSubarrays is less than two, return -1.
    • Initialize a variable minTotalLength to a very large value (infinity).
    • Use nested loops to iterate through every unique pair of sub-arrays from the validSubarrays list.
    • For each pair, check if they are non-overlapping. Two sub-arrays (start1, end1) and (start2, end2) are non-overlapping if end1 < start2 or end2 < start1.
    • If they do not overlap, calculate the sum of their lengths and update minTotalLength if this sum is smaller than the current minimum.
  • Step 3: Return the result.
    • If minTotalLength was never updated (i.e., it's still infinity), it means no non-overlapping pairs were found. Return -1.
    • Otherwise, return minTotalLength.

Walkthrough

The logic is straightforward. We first pre-process the array to find all sub-arrays that meet the sum requirement. Since all array elements are positive, we can use an efficient sliding window technique for this discovery phase, which takes linear time. After collecting all valid sub-arrays (storing their start and end indices), we perform a brute-force check. We compare every sub-array with every other sub-array. For each pair, we verify if they are non-overlapping. If they are, we calculate the sum of their lengths and keep track of the minimum sum found across all valid non-overlapping pairs.

import java.util.ArrayList;import java.util.List; class Solution {    public int minSumOfLengths(int[] arr, int target) {        List<int[]> intervals = new ArrayList<>();        int left = 0, sum = 0;        // Step 1: Find all target-sum sub-arrays        for (int right = 0; right < arr.length; right++) {            sum += arr[right];            while (sum > target) {                sum -= arr[left++];            }            if (sum == target) {                intervals.add(new int[]{left, right});            }        }         if (intervals.size() < 2) {            return -1;        }         int minLen = Integer.MAX_VALUE;        // Step 2: Check all pairs        for (int i = 0; i < intervals.size(); i++) {            for (int j = i + 1; j < intervals.size(); j++) {                int[] interval1 = intervals.get(i);                int[] interval2 = intervals.get(j);                // Check for non-overlapping. Since intervals are sorted by start index,                // we only need to check if the end of the first is before the start of the second.                if (interval1[1] < interval2[0]) {                    int len1 = interval1[1] - interval1[0] + 1;                    int len2 = interval2[1] - interval2[0] + 1;                    minLen = Math.min(minLen, len1 + len2);                }            }        }         // Step 3: Return result        return minLen == Integer.MAX_VALUE ? -1 : minLen;    }}

Complexity

Time

O(N + k^2), where N is the length of the array and k is the number of sub-arrays with the target sum. The first step (finding sub-arrays) is O(N). The second step (pairing them) is O(k^2). In the worst case, k can be O(N), making the total complexity O(N^2).

Space

O(k), where k is the number of sub-arrays with the target sum. In the worst case, k can be O(N), leading to O(N) space complexity.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

Cons

  • The time complexity is O(N^2) in the worst case, which is too slow for the given constraints (N up to 10^5).

  • It can be memory-intensive if there are many sub-arrays that sum to the target.

Solutions

class Solution {public  int minSumOfLengths(int[] arr, int target) {    Map<Integer, Integer> d = new HashMap<>();    d.put(0, 0);    int n = arr.length;    int[] f = new int[n + 1];    final int inf = 1 << 30;    f[0] = inf;    int s = 0, ans = inf;    for (int i = 1; i <= n; ++i) {      int v = arr[i - 1];      s += v;      f[i] = f[i - 1];      if (d.containsKey(s - target)) {        int j = d.get(s - target);        f[i] = Math.min(f[i], i - j);        ans = Math.min(ans, f[j] + i - j);      }      d.put(s, i);    }    return ans > n ? -1 : ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem