# Find Two Non-overlapping Sub-arrays Each With Target Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum)
Canonical: https://scaleengineer.com/dsa/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## Problem
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
## Brute Force with Pre-computation
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Two-Pass Dynamic Programming
This approach improves upon the brute-force method by using dynamic programming. The core idea is to pre-calculate the best possible sub-array choices for any "split point" in the array. We make two passes: one from left-to-right to find the minimum length of a target-sum sub-array in any prefix `arr[0...i]`, and another from right-to-left for any suffix `arr[i...n-1]`. With this pre-computed information, we can check every possible split point and find the minimum total length in a final linear-time pass.
**Time:** O(N). Each of the three passes (left-to-right, right-to-left, and combining) takes O(N) time. · **Space:** O(N) to store the `left` and `right` DP arrays.
**Pros:** Efficient O(N) time complexity, which passes the given constraints.; The logic is clear as it separates the problem into distinct, manageable passes.
**Cons:** Requires O(N) extra space for the DP arrays.; Involves multiple passes over the array, which can be slightly less performant than a single-pass solution.
### Explanation
The problem asks for two non-overlapping sub-arrays. This means one sub-array must lie completely to the left of the other. This suggests we can iterate through all possible 'split points' in the array. For a split between index `i` and `i+1`, we need the shortest target-sum sub-array in `arr[0...i]` and the shortest target-sum sub-array in `arr[i+1...n-1]`. 

This approach pre-computes these values. The `left[i]` array stores the length of the shortest target-sum sub-array found anywhere from index 0 up to `i`. The `right[i]` array stores the same, but for the range from `i` to the end of the array. After populating these two arrays, a final loop combines the results: for each `i`, `left[i] + right[i+1]` gives the sum of lengths for the best pair separated at `i`. We take the minimum over all possible `i`.

```java
import java.util.Arrays;

class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        
        // Step 1: Calculate prefix minimums
        int[] left = new int[n];
        Arrays.fill(left, Integer.MAX_VALUE);
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        int l = 0;
        for (int r = 0; r < n; r++) {
            sum += arr[r];
            while (sum > target) {
                sum -= arr[l++];
            }
            if (sum == target) {
                minLen = Math.min(minLen, r - l + 1);
            }
            left[r] = minLen;
        }

        // Step 2: Calculate suffix minimums
        int[] right = new int[n];
        Arrays.fill(right, Integer.MAX_VALUE);
        minLen = Integer.MAX_VALUE;
        sum = 0;
        int r = n - 1;
        for (l = n - 1; l >= 0; l--) {
            sum += arr[l];
            while (sum > target) {
                sum -= arr[r--];
            }
            if (sum == target) {
                minLen = Math.min(minLen, r - l + 1);
            }
            right[l] = minLen;
        }

        // Step 3: Combine results
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            if (left[i] != Integer.MAX_VALUE && right[i + 1] != Integer.MAX_VALUE) {
                result = Math.min(result, left[i] + right[i + 1]);
            }
        }

        // Step 4: Return final answer
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}
```
### Algorithm
*   **Step 1: Calculate Prefix Minimums (`left` array).**
    *   Create an array `left` of size `n`, initialized with a large value (infinity). `left[i]` will store the minimum length of a target-sum sub-array found in the prefix `arr[0...i]`.
    *   Populate `left` by iterating from `i=0` to `n-1`. Use a sliding window to find target-sum sub-arrays. Maintain a variable `minLenSoFar` and for each `i`, set `left[i] = minLenSoFar`.
*   **Step 2: Calculate Suffix Minimums (`right` array).**
    *   Create an array `right` of size `n`, initialized with infinity. `right[i]` will store the minimum length of a target-sum sub-array within the suffix `arr[i...n-1]`.
    *   Populate `right` by iterating from `i=n-1` down to `0`, using a similar sliding window approach.
*   **Step 3: Combine Results.**
    *   Initialize `result = infinity`.
    *   Iterate with an index `i` from `0` to `n-2`. This index `i` represents a potential split point in the array.
    *   For each `i`, we consider one sub-array from the left part `arr[0...i]` and one from the right part `arr[i+1...n-1]`.
    *   The minimum length of a sub-array in the left part is `left[i]`, and in the right part is `right[i+1]`.
    *   If both `left[i]` and `right[i+1]` are valid (not infinity), it means we can form a valid pair. Update `result = min(result, left[i] + right[i+1])`.
*   **Step 4: Return the final answer.**
    *   If `result` was updated, return it. Otherwise, return -1.

## One-Pass Dynamic Programming
This is the most optimized approach, solving the problem in a single pass. It uses a dynamic programming strategy combined with a sliding window. As we iterate through the array from left to right, we maintain a DP array that stores the minimum length of a target-sum sub-array found up to the current position. When the sliding window finds a new target-sum sub-array, we can immediately use the DP array to find the best non-overlapping sub-array to its left and update our answer.
**Time:** O(N). We iterate through the array once, and the sliding window pointers `left` and `right` each traverse the array at most once. · **Space:** O(N) for the `dp` array.
**Pros:** Most efficient time complexity at O(N).; Solves the problem in a single pass over the data.; Elegant combination of sliding window and dynamic programming.
**Cons:** Requires O(N) extra space for the DP array.; The logic is slightly more condensed, which might be harder to debug than the two-pass approach.
### Explanation
This approach cleverly combines the computation and result-finding steps. We use a single loop and a sliding window to find sub-arrays summing to `target`. A DP array, `dp`, is maintained where `dp[i]` stores the minimum length of a valid sub-array in the prefix `arr[0...i]`. 

When our sliding window `[left, right]` finds a sub-array with the target sum, we know this sub-array could be the 'right' part of our final pair. The best 'left' part must be a sub-array that ends at or before index `left - 1`. The minimum length for such a sub-array is precisely what we have stored in `dp[left - 1]`. We can thus immediately calculate a candidate for the total minimum length (`currentLen + dp[left - 1]`) and update our overall result. At the end of each iteration `right`, we update `dp[right]` with the minimum length found so far, ensuring it's ready for future calculations.

```java
import java.util.Arrays;

class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        int result = Integer.MAX_VALUE;
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            sum += arr[right];
            
            while (sum > target) {
                sum -= arr[left++];
            }
            
            if (sum == target) {
                int currentLen = right - left + 1;
                // Check for a non-overlapping sub-array on the left
                if (left > 0 && dp[left - 1] != Integer.MAX_VALUE) {
                    result = Math.min(result, currentLen + dp[left - 1]);
                }
                // Update the minimum length found so far
                minLen = Math.min(minLen, currentLen);
            }
            
            // Update the DP array for the current position
            dp[right] = minLen;
        }
        
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}
```
### Algorithm
*   **Step 1: Initialization.**
    *   Create a DP array `dp` of size `n`, initialized to infinity. `dp[i]` will store the minimum length of a target-sum sub-array in `arr[0...i]`.
    *   Initialize `result = infinity` to store the final answer.
    *   Initialize `minLen = infinity` to track the minimum length of any target-sum sub-array found so far.
    *   Initialize a sliding window with `left = 0` and `sum = 0`.
*   **Step 2: Single Pass Iteration.**
    *   Iterate through the array with a `right` pointer from `0` to `n-1`.
    *   In each iteration, add `arr[right]` to `sum`.
    *   While `sum > target`, shrink the window from the left by subtracting `arr[left]` and incrementing `left`.
    *   If `sum == target`, we have found a sub-array `arr[left...right]`.
        *   Let its length be `currentLen = right - left + 1`.
        *   Now, we look for a non-overlapping sub-array to its left. The best one must end at or before index `left - 1`. The minimum length for such a sub-array is already computed and stored in `dp[left - 1]`.
        *   If `left > 0` and `dp[left - 1]` is not infinity, we have found a valid pair. Update `result = min(result, currentLen + dp[left - 1])`.
        *   Update the overall minimum length found so far: `minLen = min(minLen, currentLen)`.
    *   After checking for a pair, update the DP array for the current position: `dp[right] = minLen`.
*   **Step 3: Return Result.**
    *   After the loop finishes, if `result` is still infinity, return -1. Otherwise, return `result`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSumOfLengths(vector<int> &arr, int target) {
    unordered_map<int, int> d;
    d[0] = 0;
    int s = 0, n = arr.size();
    int f[n + 1];
    const int inf = 1 << 30;
    f[0] = inf;
    int ans = inf;
    for (int i = 1; i <= n; ++i) {
      int v = arr[i - 1];
      s += v;
      f[i] = f[i - 1];
      if (d.count(s - target)) {
        int j = d[s - target];
        f[i] = min(f[i], i - j);
        ans = min(ans, f[j] + i - j);
      }
      d[s] = i;
    }
    return ans > n ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int: d = {0: 0} s, n = 0, len(arr) f = [inf] * (n + 1) ans = inf for i, v in enumerate(arr, 1): s += v f[i] = f[i - 1] if s - target in d: j = d[s - target] f[i] = min(f[i], i - j) ans = min(ans, f[j] + i - j) d[s] = i return - 1 if ans > n else ans

```