Find Two Non-overlapping Sub-arrays Each With Target Sum
MediumUpdated: Aug 2, 2025
Practice on:
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
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 <= 10^51 <= arr[i] <= 10001 <= 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
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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 }
}
}
TypeScript
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.