Minimum Size Subarray Sum: Shrink Greedily, Count Carefully

"Minimum Size Subarray Sum" shows up again and again in Meta, Google, Goldman Sachs phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Sliding Window pattern quickly and code it cleanly. Part 3 of 11 in the Sliding Window arc.

The Problem

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target, or 0 if none exists. Positivity of the elements is doing quiet, load-bearing work here.

Input:  target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
The subarray [4, 3] has sum 7 and minimal length.

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Shortest window satisfying a threshold flips the usual template: instead of shrinking when invalid, you shrink while valid to squeeze the window to its minimum before recording. Positive numbers make the window sum monotonic under both moves, which is what legitimizes the greedy shrink.

The Approach

Expand right, adding to a running sum. While the sum meets the target, record the window length and remove nums[left] — every removal strictly decreases the sum, so the while loop is safe and each element leaves the window at most once.

Then be ready for the killer follow-up: with negative numbers the monotonicity dies and the pattern with it — the fix is prefix sums with a monotonic deque, and just naming that is often the difference-maker.

Python Solution

def min_subarray_len(target: int, nums: list[int]) -> int:
    """Minimal length of a contiguous subarray with sum >= target."""
    left = 0
    window = 0
    best = float("inf")
    for right, value in enumerate(nums):
        window += value
        while window >= target:
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1
    return 0 if best == float("inf") else int(best)

Complexity

• Time: O(n) — each index enters the window once and leaves at most once
• Space: O(1) — running sum plus two indices

Interview Tips and Follow-Ups

• Say why positivity matters before being asked: without it the shrink is unsound. This is the highest-value sentence in the interview.
• The negative-numbers variant (LeetCode 862) uses prefix sums plus a monotonic deque — know it as the escalation.
• Off-by-one check: record the length before shrinking past validity, inside the while loop.

If this clicked, continue the Sliding Window arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.