Sliding window: minimum size subarray sum
Sliding window: minimum size subarray sum
A sliding window is a sub-range [left, right] that you grow on the right
and shrink on the left, so you never re-scan the same elements. It turns many
"find the best contiguous run" problems from O(n²) into a single O(n) pass.
The trick for minimum-length problems: keep expanding the window until it's "good enough", then shrink from the left as far as you can while it stays good — recording the smallest width you ever saw.
total = 0
total += nums[right] # grow on the right
while total >= target: # window is good → try to make it smaller
total -= nums[left] # shrink on the left
left += 1
Your task
Write min_subarray_len(target, nums) that returns the length of the shortest
contiguous subarray whose sum is ≥ target. If no such subarray exists,
return 0. All numbers are positive.
min_subarray_len(7, [2, 3, 1, 2, 4, 3]) # 2 -> [4, 3]
min_subarray_len(4, [1, 4, 4]) # 1 -> [4]
min_subarray_len(11, [1, 1, 1, 1, 1]) # 0 -> never reaches 11
Hint: one pass, two indices. Add to a running total as right advances; while
total >= target, record right - left + 1 and slide left forward.
Tests
- classic [4,3]
- single big element
- never reaches
- whole array (hidden)
- impossible (hidden)
- exact single (hidden)
Stuck? Ask for a spark
$ Console output will appear here.