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

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.

Examples

Example 1

1
2
3


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

1
2
3


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

1
2
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 <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

Solution

Method 1 – Sliding Window + Prefix Min Array

Intuition

We want to find two non-overlapping subarrays each summing to target, with the minimum total length. We can use a sliding window to find all subarrays with sum = target, and for each ending index, keep track of the shortest subarray found so far. Then, for each subarray found, check if there is a non-overlapping subarray before it.

Approach

Use a sliding window to find all subarrays with sum = target.
For each subarray ending at index i, keep track of the minimum length of a subarray ending at or before i.
For each subarray found, if there is a non-overlapping subarray before it, update the answer with the sum of their lengths.
Return the minimum sum found, or -1 if not possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n = arr.size(), ans = INT_MAX;
        vector<int> minLen(n, INT_MAX);
        int l = 0, sum = 0, best = INT_MAX;
        for (int r = 0; r < n; ++r) {
            sum += arr[r];
            while (sum > target) sum -= arr[l++];
            if (sum == target) {
                int currLen = r - l + 1;
                if (l > 0 && minLen[l-1] != INT_MAX)
                    ans = min(ans, currLen + minLen[l-1]);
                best = min(best, currLen);
            }
            minLen[r] = best;
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func minSumOfLengths(arr []int, target int) int {
    n := len(arr)
    minLen := make([]int, n)
    for i := range minLen {
        minLen[i] = 1 << 30
    }
    l, sum, best, ans := 0, 0, 1<<30, 1<<30
    for r := 0; r < n; r++ {
        sum += arr[r]
        for sum > target {
            sum -= arr[l]
            l++
        }
        if sum == target {
            currLen := r - l + 1
            if l > 0 && minLen[l-1] < 1<<30 {
                if ans > currLen+minLen[l-1] {
                    ans = currLen + minLen[l-1]
                }
            }
            if best > currLen {
                best = currLen
            }
        }
        minLen[r] = best
    }
    if ans == 1<<30 {
        return -1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length, ans = Integer.MAX_VALUE;
        int[] minLen = new int[n];
        Arrays.fill(minLen, Integer.MAX_VALUE);
        int l = 0, sum = 0, best = Integer.MAX_VALUE;
        for (int r = 0; r < n; r++) {
            sum += arr[r];
            while (sum > target) sum -= arr[l++];
            if (sum == target) {
                int currLen = r - l + 1;
                if (l > 0 && minLen[l-1] != Integer.MAX_VALUE)
                    ans = Math.min(ans, currLen + minLen[l-1]);
                best = Math.min(best, currLen);
            }
            minLen[r] = best;
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    fun minSumOfLengths(arr: IntArray, target: Int): Int {
        val n = arr.size
        val minLen = IntArray(n) { Int.MAX_VALUE }
        var l = 0
        var sum = 0
        var best = Int.MAX_VALUE
        var ans = Int.MAX_VALUE
        for (r in 0 until n) {
            sum += arr[r]
            while (sum > target) {
                sum -= arr[l++]
            }
            if (sum == target) {
                val currLen = r - l + 1
                if (l > 0 && minLen[l-1] != Int.MAX_VALUE)
                    ans = minOf(ans, currLen + minLen[l-1])
                best = minOf(best, currLen)
            }
            minLen[r] = best
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def minSumOfLengths(self, arr: list[int], target: int) -> int:
        n = len(arr)
        min_len = [float('inf')] * n
        l = 0
        s = 0
        best = float('inf')
        ans = float('inf')
        for r in range(n):
            s += arr[r]
            while s > target:
                s -= arr[l]
                l += 1
            if s == target:
                curr = r - l + 1
                if l > 0 and min_len[l-1] != float('inf'):
                    ans = min(ans, curr + min_len[l-1])
                best = min(best, curr)
            min_len[r] = best
        return -1 if ans == float('inf') else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


impl Solution {
    pub fn min_sum_of_lengths(arr: Vec<i32>, target: i32) -> i32 {
        let n = arr.len();
        let mut min_len = vec![i32::MAX; n];
        let (mut l, mut s, mut best, mut ans) = (0, 0, i32::MAX, i32::MAX);
        for r in 0..n {
            s += arr[r];
            while s > target {
                s -= arr[l];
                l += 1;
            }
            if s == target {
                let curr = (r - l + 1) as i32;
                if l > 0 && min_len[l-1] != i32::MAX {
                    ans = ans.min(curr + min_len[l-1]);
                }
                best = best.min(curr);
            }
            min_len[r] = best;
        }
        if ans == i32::MAX { -1 } else { ans }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    minSumOfLengths(arr: number[], target: number): number {
        const n = arr.length;
        const minLen = new Array(n).fill(Infinity);
        let l = 0, s = 0, best = Infinity, ans = Infinity;
        for (let r = 0; r < n; r++) {
            s += arr[r];
            while (s > target) s -= arr[l++];
            if (s === target) {
                const curr = r - l + 1;
                if (l > 0 && minLen[l-1] !== Infinity)
                    ans = Math.min(ans, curr + minLen[l-1]);
                best = Math.min(best, curr);
            }
            minLen[r] = best;
        }
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

⏰ Time complexity: O(n), since each element is processed at most twice by the sliding window.
🧺 Space complexity: O(n), for the prefix min array.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Sliding Window + Prefix Min Array#

Intuition#

Approach#

Code#

Complexity#