Minimum Size Subarray Sum: Sliding Window in Action

LeetCode's Minimum Size Subarray Sum (problem 209) asks: given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

For example, given nums = [2,3,1,2,4,3] and target = 7, the answer is 2 because the subarray [4,3] sums to 7 with just two elements.

Why this problem matters

This is one of the cleanest demonstrations of the "shrinking window" variant of the sliding window pattern. In problems like Longest Substring Without Repeating Characters, you grow the window as large as possible and only shrink when the window becomes invalid. Here it is the opposite: you grow until the window becomes valid, then shrink while it stays valid to find the minimum length.

Understanding both variants is critical. Many candidates learn sliding window as a single technique, but there are really two flavors: growing windows (maximize something) and shrinking windows (minimize something). This problem drills the shrinking variant in its purest form, with no extra data structures needed beyond a running sum.

If you can solve this problem cleanly, you have the foundation to tackle harder variants like Minimum Window Substring, where the validity condition involves frequency matching instead of a simple sum.

Thinking it through

Every element in the array is positive. That means as you expand the window to the right, the sum can only increase. As you shrink from the left, the sum can only decrease. This monotonic behavior is exactly what makes the sliding window work: once a window becomes valid (sum >= target), shrinking it will eventually make it invalid, and you never need to go back.

The strategy is: keep expanding right until the window sum reaches the target, then shrink left as far as you can while the sum still meets the target. Each time you have a valid window, check if its length is the new minimum.

Brute force: check every subarray

The naive approach tries every possible start and end position:

def minSubArrayLen(target, nums):
    n = len(nums)
    best = float("inf")
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            if current_sum >= target:
                best = min(best, j - i + 1)
                break
    return best if best != float("inf") else 0

This runs in O(n^2) time. For every starting index, you scan forward until the sum hits the target. It works, but you are repeating a lot of computation. When you move from start index i to i+1, you throw away the entire running sum and rebuild it from scratch.

Sliding window: expand and shrink

Instead of restarting for each position, maintain a window with two pointers. Advance right to grow the window and add to the running sum. Whenever the sum meets the target, record the window length and advance left to shrink the window, subtracting the removed element from the sum. Keep shrinking as long as the sum still meets the target.

Because every element is positive, the sum decreases monotonically as you shrink. Once the sum drops below the target, you stop shrinking and go back to expanding. Both pointers only move forward, so the total work across the entire array is O(n).

def minSubArrayLen(target, nums):
    left = 0
    current_sum = 0
    best = float("inf")

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum >= target:
            best = min(best, right - left + 1)
            current_sum -= nums[left]
            left += 1

    return best if best != float("inf") else 0

The inner while loop is the key difference from the "growing window" variant. In growing window problems, the inner loop fires when the window is invalid (to restore validity). Here, it fires when the window is valid (to find the smallest valid window). This is the shrinking window template.

Complexity analysis

Time: O(n). Each element is visited at most twice, once when right passes over it and once when left passes over it. The two pointers each traverse the array at most once.

Space: O(1). We only use a few variables: left, current_sum, and best. No extra data structures.

Edge cases to watch for

• No valid subarray: if the total sum of the entire array is less than target, return 0. The best = float("inf") check handles this.
• Single element meets target: if any single element is >= target, the answer is 1. The shrinking loop naturally finds this.
• Entire array is needed: if only the full array sums to >= target, the answer is n. The window expands to the end before any shrinking produces a valid window.
• All elements equal target: every single element is a valid window of length 1. The first shrink step after expanding to index 0 already captures this.

The building blocks

This problem decomposes into two reusable pieces:

1. Running sum maintenance

As the window expands, add the new element. As it shrinks, subtract the removed element. This incremental update avoids recalculating the sum from scratch each time.

current_sum += nums[right]

current_sum -= nums[left]
left += 1

This same add-on-expand, subtract-on-shrink pattern shows up whenever you need to track a numeric aggregate over a window. In Maximum Subarray, the aggregate is handled differently (Kadane's algorithm resets instead of shrinking), but the idea of maintaining a running value is the same core skill.

2. Shrinking window mechanics

The two-pointer structure where right always advances and left advances only when the window is valid. The inner loop shrinks while valid, recording each valid window length. This is the mirror image of the growing window template.

for right in range(len(nums)):
    current_sum += nums[right]
    while window_is_valid():
        record_result()
        shrink_from_left()

In Minimum Window Substring, the same shrinking template appears but with a frequency map instead of a simple sum. In Longest Repeating Character Replacement, you see the growing variant instead. Recognizing which variant a problem needs is half the battle.

From understanding to recall

Reading through this solution once gives you the idea. But in an interview next month, will you remember whether to shrink while valid or while invalid? Will you remember to check for float("inf") at the end? Spaced repetition locks in these details by having you reconstruct the solution at increasing intervals. Each repetition reinforces the shrinking window template until it becomes automatic, not something you have to re-derive under pressure.

Related posts

• Minimum Window Substring - The harder shrinking window variant with frequency matching
• Longest Substring Without Repeating Characters - The growing window variant, a great comparison
• Maximum Subarray - Another subarray problem using Kadane's algorithm instead of sliding window