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 (LeetCode 209) ───

# Pattern: Sliding window — expand right, shrink while sum >= target

# Time: O(n) Space: O(1)

# 1. Define: minSubArrayLen(target, nums)

# 2. Init: left=0, sum=0, minLen=inf

# 3. Expand right: for right in range(len(nums)):

# sum += nums[right]

# 4. Shrink while valid: while sum >= target:

# minLen = min(minLen, right-left+1); sum -= nums[left]; left += 1

# 5. Return: return minLen if minLen != inf else 0

# Vars: left, right, sum, minLen

▼ your implementation ▼

Verify your solution: