Minimum Size Subarray Sum: The Shrinking Sliding Window

Given positive integers nums and a target, return the length of the shortest contiguous subarray whose sum is at least the target, or 0 if none exists.

Two pointers that only move forward

Grow the window with the right pointer. As soon as the sum reaches the target, record the length and shrink from the left while it still holds.

def min_sub_array_len(target, nums):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

Why it is O(n)

Each index enters the window once and leaves once, so the nested loop does at most 2n steps. Say this before the interviewer asks about the inner while loop.

The condition that makes it work

All numbers are positive, so adding elements only increases the sum and removing them only decreases it. With negatives the window loses that monotonic property; you would need prefix sums with a monotonic deque instead (the LeetCode 862 variant).

Follow-up: O(n log n)

Build prefix sums, then for each start binary search for the first prefix at least prefix[i] + target. It is slower but a good answer when asked for a second approach.

Written by the team behind real-time interview help, which builds tools for interview practice. Notes are original and free to share.