Minimum Size Subarray Sum

LeetCode 209 • Medium • Sliding Window

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is ≥ target. If none, return 0.

TimeO(n)each element at most 2x

SpaceO(1)iterative; O(n) recursive stack

Window: — Sum: — MinLen: —

Window

Right (expand)

Shrink

Result

Window

—

Sum

—

MinLen

—

Speed:

Ready

Press Play. Expand right, add to sum. While sum ≥ target, shrink from left and update min length.

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.

═══ MIN SUBARRAY SUM — SLIDING WINDOW ═══

PATTERN ▸ Expand right, shrink while sum >= target O(n) · O(1)

① INIT

left=0, sum=0, minLen=inf

② EXPAND RIGHT

for right in range(len(nums)):

sum += nums[right]

③ SHRINK WHILE VALID

while sum >= target:

minLen = min(minLen, right-left+1)

sum -= nums[left]; left += 1

④ RETURN

return minLen if minLen != inf else 0

▼ your implementation ▼

Verify your solution: