Find two non overlapping sub arrays each with target sum

Array Hash Table Binary Search Dynamic Programming Sliding Window

36.7% acceptance

Feb 25, 2026

1767

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_sum_of_lengths(arr: Vec<i32>, target: i32) -> i32 {
    let n = arr.len();
    let inf = i32::MAX / 2;
    let mut left = vec![inf; n];
    let (mut l, mut sum) = (0usize, 0i32);
    for r in 0..n {
      sum += arr[r];
      while sum > target { sum -= arr[l]; l += 1; }
      if sum == target {
        left[r] = (r - l + 1) as i32;
      }
      if r > 0 && left[r - 1] < left[r] {
        left[r] = left[r - 1];
      }
    }
    let mut right = vec![inf; n];
    let (mut l2, mut sum2) = (0usize, 0i32);
    for r in 0..n {
      sum2 += arr[r];
      while sum2 > target { sum2 -= arr[l2]; l2 += 1; }
      if sum2 == target {
        right[l2] = (r - l2 + 1) as i32;
      }
    }
    for i in (0..n - 1).rev() {
      if right[i + 1] < right[i] { right[i] = right[i + 1]; }
    }
    let mut ans = inf;
    for i in 0..n - 1 {
      if left[i] < inf && right[i + 1] < inf {
        ans = ans.min(left[i] + right[i + 1]);
      }
    }
    if ans == inf { -1 } else { ans }
  }
}