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

medium sliding window prefix minimum dynamic programming

Problem

Given an array of positive integers arr and an integer target, find two non-overlapping sub-arrays that each sum to exactly target, chosen so the sum of their two lengths is minimum. Return that minimum total length, or -1 if two such sub-arrays do not exist.

Inputarr = [3,2,2,4,3], target = 3

Output2

Only two sub-arrays have sum 3: the leading [3] and trailing [3]. Their lengths add to 1 + 1 = 2.

arr (comma-separated positives)

target

def minSumOfLengths(arr, target):
    n = len(arr)
    INF = float('inf')
    best = [INF] * n          # best[i] = min length ending at or before i
    res = INF
    best_so_far = INF
    left = 0
    cur = 0
    for right in range(n):
        cur += arr[right]            # grow window to the right
        while cur > target:          # shrink while sum too large
            cur -= arr[left]
            left += 1
        if cur == target:            # found a window summing to target
            length = right - left + 1
            if left > 0 and best[left - 1] != INF:
                res = min(res, best[left - 1] + length)
            best_so_far = min(best_so_far, length)
        best[right] = best_so_far    # carry the running minimum forward
    return res if res != INF else -1

function minSumOfLengths(arr, target) {
  const n = arr.length, INF = Infinity;
  const best = new Array(n).fill(INF); // best[i]=min len ending at/before i
  let res = INF, bestSoFar = INF;
  let left = 0, cur = 0;
  for (let right = 0; right < n; right++) {
    cur += arr[right];                 // grow window to the right
    while (cur > target) {             // shrink while sum too large
      cur -= arr[left];
      left++;
    }
    if (cur === target) {              // window sums to target
      const length = right - left + 1;
      if (left > 0 && best[left - 1] !== INF)
        res = Math.min(res, best[left - 1] + length);
      bestSoFar = Math.min(bestSoFar, length);
    }
    best[right] = bestSoFar;           // carry running minimum forward
  }
  return res === INF ? -1 : res;
}

int minSumOfLengths(int[] arr, int target) {
    int n = arr.length, INF = Integer.MAX_VALUE;
    int[] best = new int[n];           // best[i]=min len ending at/before i
    int res = INF, bestSoFar = INF;
    int left = 0, cur = 0;
    for (int right = 0; right < n; right++) {
        cur += arr[right];             // grow window to the right
        while (cur > target) {         // shrink while sum too large
            cur -= arr[left];
            left++;
        }
        if (cur == target) {           // window sums to target
            int length = right - left + 1;
            if (left > 0 && best[left - 1] != INF)
                res = Math.min(res, best[left - 1] + length);
            bestSoFar = Math.min(bestSoFar, length);
        }
        best[right] = bestSoFar;       // carry running minimum forward
    }
    return res == INF ? -1 : res;
}

int minSumOfLengths(vector<int>& arr, int target) {
    int n = arr.size();
    const int INF = INT_MAX;
    vector<int> best(n, INF);           // best[i]=min len ending at/before i
    int res = INF, bestSoFar = INF;
    int left = 0, cur = 0;
    for (int right = 0; right < n; right++) {
        cur += arr[right];             // grow window to the right
        while (cur > target) {         // shrink while sum too large
            cur -= arr[left];
            left++;
        }
        if (cur == target) {           // window sums to target
            int length = right - left + 1;
            if (left > 0 && best[left - 1] != INF)
                res = min(res, best[left - 1] + length);
            bestSoFar = min(bestSoFar, length);
        }
        best[right] = bestSoFar;       // carry running minimum forward
    }
    return res == INF ? -1 : res;
}

Explanation

Because every value is positive, the prefix sum is strictly increasing, so a sliding window finds all sub-arrays equal to target in one left-to-right pass. We expand the window by adding arr[right], and whenever the running sum cur exceeds target we drop elements from the left until it no longer does.

The trick is pairing windows that do not overlap. We keep best[i] = the smallest length of any valid sub-array that ends at index i or earlier. This is a prefix-minimum (a one-dimensional DP carried in best_so_far).

When the current window [left, right] sums to target, it is a candidate for the second sub-array. The best non-overlapping partner ending strictly before left has length best[left - 1]. So best[left - 1] + (right - left + 1) is a candidate answer, and we minimise it into res.

After considering the window, we update best_so_far with the current window length and store it into best[right], so later windows can use this one as their left partner.

Example arr = [3,2,2,4,3], target = 3: the window [3] at index 0 sets best = 1. The window [3] at index 4 pairs with best[3] = 1, giving 1 + 1 = 2, the minimum.

Time: O(n) Space: O(n)