LeetCode #209 Medium

Minimum Size Subarray Sum

Find the length of the shortest contiguous subarray whose sum is at least target, or 0 if none exists.

arraysliding-windowtwo-pointersprefix-sum

02

Intuition

💡

You will get the shape of this right and the shrink wrong. The natural code is: extend the window by one element, and then if the sum is at least the target, record the length and advance left once. That if is the bug. A single new element can make several leading elements redundant at the same time, not just one. Take nums = [1,1,1,1,1,8] with target 8. When the 8 arrives the sum is 13, and you need to drop the 1 at the front, and the next 1, and the next, all the way down until only the 8 remains and the answer is 1. An if stops after the first drop and reports 5. Change it to a while and the window keeps contracting for as long as it still clears the target. That costs nothing asymptotically, because left only ever moves forward: each index enters the window once and leaves once, so the nested loop is still O(n) overall. The invariant is that after every iteration of the outer loop, the window is the shortest suffix ending at right whose sum still meets the target.

03

Approach

1

Grow on the right, unconditionally

Walk right across the array adding nums[right] to a running sum. Growing is always safe because all values are positive, so extending can only increase the sum and can only move you closer to meeting the target. There is no decision to make here, which is why the whole difficulty concentrates in the shrink.

2

Shrink on the left with a while, not an if

While the sum is still at least the target, the current window is a valid candidate, so record its length against the running best, then subtract nums[left] and advance left. Repeat. Recording before shrinking matters, because the window is valid at the moment you measure it. The loop exits when the sum drops below target, meaning the window is now minimal for this right endpoint.

3

Track the best and translate infinity to zero

Keep best initialised to infinity and take the minimum on each valid window. If the loop finishes with best still infinite, no subarray anywhere reached the target and the problem asks for 0 rather than a sentinel, so convert at the end. This single conversion is cleaner than special-casing the empty answer inside the loop.

04

Solution & live demo

python

▶1class Solution:
▶2    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
▶3        left, total = 0, 0
▶4        best = float('inf')
▶5        for right in range(len(nums)):
▶6            total += nums[right]
▶7            while total >= target:
▶8                best = min(best, right - left + 1)
▶9                total -= nums[left]
▶10                left += 1
▶11        return 0 if best == float('inf') else best

05

Edge cases

Total sum below target

The shrink loop never runs, best stays infinite, and the final conversion returns 0.

A single element already at or above target

The shrink fires immediately and records length 1, which is the global minimum and cannot be beaten.

One large value after many small ones

The while shrink drops several leading elements in a row on the same right pointer, which is exactly what an if would get wrong.

Empty array

The outer loop body never executes and the infinity to zero conversion returns 0.

06

Complexity

Time

O(n)

Space

O(1)

Left never moves backwards, so despite the nested while each index is added once and removed once.