Find Two Non-overlapping Sub-arrays Each With Target Sum: Sliding Window Meets Prefix Minimum

You are given an array of positive integers arr and an integer target. You need to find two non-overlapping sub-arrays, each with a sum equal to target, such that the total length of the two sub-arrays is minimized. Return the minimum total length, or -1 if no such pair exists.

This is LeetCode 1477: Find Two Non-overlapping Sub-arrays Each With Target Sum.

For example, given arr = [3, 2, 2, 4, 3] and target = 3, the two shortest non-overlapping subarrays that each sum to 3 are [3] at index 0 and [3] at index 4. The minimum combined length is 1 + 1 = 2.

Why this problem matters

At first glance, this looks like a brute-force search: find all subarrays that sum to the target, then try every pair. But that approach quickly blows up in time complexity. The real challenge is combining two techniques, sliding window and dynamic programming, into a single clean pass.

This problem teaches you how to think about "left-side state" while processing rightward. You are not just finding subarrays. You are finding the best subarray that ended before your current position, and combining it with the subarray you just found. That "prefix minimum" idea shows up in tons of optimization problems.

Once you internalize this pattern, you will recognize it in problems like partitioning arrays into segments with constraints, or any scenario where you need to pick two non-overlapping structures that together minimize (or maximize) some quantity.

The key insight

Since every element in arr is positive, you can use a sliding window to find all subarrays with sum equal to target. As you slide the right pointer forward, you shrink from the left whenever the window sum exceeds the target.

The trick is tracking what happened before the current window. Maintain an array bestAtOrBefore[i] that stores the length of the shortest subarray with sum = target that ends at or before index i. When your sliding window finds a match at [left..right], you check bestAtOrBefore[left - 1]. If that value is not infinity, you have found a valid non-overlapping pair, and the total length is bestAtOrBefore[left - 1] + (right - left + 1).

By keeping a running prefix minimum, you ensure bestAtOrBefore[i] always reflects the globally best subarray ending anywhere up to index i, not just exactly at i. This is what makes the single-pass approach work.

The solution

def min_sum_of_lengths(arr, target):
    n = len(arr)
    best = [float('inf')] * n
    ans = float('inf')
    window_sum = 0
    left = 0

    for right in range(n):
        window_sum += arr[right]

        while window_sum > target:
            window_sum -= arr[left]
            left += 1

        if window_sum == target:
            cur_len = right - left + 1
            if left > 0 and best[left - 1] < float('inf'):
                ans = min(ans, best[left - 1] + cur_len)
            best[right] = cur_len
        else:
            best[right] = float('inf')

        if right > 0:
            best[right] = min(best[right], best[right - 1])

    return ans if ans < float('inf') else -1

Here is how each piece works.

The sliding window expands by adding arr[right] and shrinks by removing arr[left] whenever the sum exceeds the target. Because all values are positive, the window sum is monotonically related to the window size, which means the window never needs to backtrack.

When window_sum == target, you have found a valid subarray [left..right]. Its length is right - left + 1. You check whether there is a shorter valid subarray that ended before left by looking at best[left - 1]. If so, you have a candidate answer.

The line best[right] = min(best[right], best[right - 1]) is the prefix minimum update. It ensures best[right] holds the shortest valid subarray ending at any index up to right, not just at right itself. Without this, you would miss cases where the optimal left-side subarray ended several indices ago.

Visual walkthrough

Let's trace through arr = [3, 2, 2, 4, 3] with target = 3. Watch how the sliding window moves across the array while the bestAtOrBefore array accumulates the prefix minimum.

Complexity analysis

Time is O(n). Each element enters and leaves the sliding window at most once, giving O(n) total work. The prefix minimum update is O(1) per element. Everything runs in a single pass.

Space is O(n) for the bestAtOrBefore array, which stores one value per index.

The building blocks

1. Sliding window for exact subarray sum

Because every element is positive, expanding the window increases the sum and shrinking it decreases the sum. This monotonic property lets you find all subarrays summing to a target in O(n) time. You will reuse this pattern in problems like "Minimum Size Subarray Sum" and "Subarray Product Less Than K."

2. Prefix minimum array

The bestAtOrBefore array is a classic prefix optimization. Instead of rescanning all previous indices every time you find a match, you maintain a running minimum. This reduces the "find the best left-side subarray" query from O(n) to O(1). The same idea appears in problems like "Best Time to Buy and Sell Stock" where you track the minimum price seen so far.

3. Combining two non-overlapping results

The key constraint is non-overlapping. By anchoring the current subarray at [left..right] and querying bestAtOrBefore[left - 1], you guarantee no overlap. This "split point" thinking, where you fix a boundary and ask "what is the best thing on each side?", comes up in partitioning problems, stock trading with cooldowns, and any problem requiring two disjoint selections.

Edge cases

• No valid subarray exists: if no subarray sums to target, return -1. The answer stays at infinity.
• Only one valid subarray: you need at least two. A single match is not enough to form a pair, so return -1.
• Entire array is one valid subarray: arr = [1, 1, 1], target = 3. Only one subarray [1,1,1] sums to 3. There is no room for a second non-overlapping one. Return -1.
• Adjacent single-element subarrays: arr = [5, 5], target = 5. Two subarrays of length 1 each. Answer is 2.
• Overlapping candidates: arr = [1, 2, 1, 2, 1], target = 3. Subarrays [1,2] appear at multiple positions. You need the combination that minimizes total length while avoiding overlap.
• Large arrays with many matches: the O(n) approach handles arrays up to 10^5 elements without issue, because every element is processed at most twice (once added, once removed from the window).

From understanding to recall

You have seen how sliding window and prefix minimum work together to solve this in one pass. The logic is elegant: find subarrays with the window, track the best-so-far with the prefix array, and combine them at each match. But reproducing this under pressure requires more than understanding.

The subtle details matter. Do you query best[left - 1] or best[left]? Do you update the prefix minimum before or after recording the current window? Do you shrink the window with while or if? These are the kinds of off-by-one issues that cost you during interviews, and they are exactly the kind of thing that spaced repetition cements.

CodeBricks breaks this problem into its sliding window and prefix minimum building blocks, then drills each one independently. You type the window expansion, the shrink logic, and the prefix update from memory until it is automatic. When a problem asks you to combine two non-overlapping results, you do not think about it. You just write it.

Related posts

• Minimum Size Subarray Sum - The foundational sliding window problem for finding subarrays with a target sum
• Subarray Sum Equals K - Uses prefix sums and hash maps to count subarrays with a given sum, even with negative numbers
• Sliding Window Pattern - A deep dive into the sliding window template that powers this and dozens of other problems