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.
In plain steps (you write the Python):
advance `right` across the list, adding each value to a running total # grow
while the total is >= target: # window is "good" — try to shrink it
record the current width (right - left + 1) if it's the smallest so far
subtract the left value from the total and move `left` forward # shrink
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
✦ Stuck? Ask for a spark
Sign in or create a free account to use your monthly AI explainer allowance.
$ Console output will appear here.