Sliding Window

Sliding window finds the best contiguous stretch of an array — shortest, longest, largest sum — in a single linear pass by keeping a movable [left, right] range and adjusting its two ends instead of re-scanning. The classic case is the shortest subarray whose sum reaches a target, in O(n) time and O(1) space.

Grow the right end to add values, shrink the left end once the window qualifies, and never look back.

Picture an inchworm crawling along the array. The front end reaches forward to cover more ground; once the worm is long enough to clear the target, the back end pulls up to make it as short as possible again. Neither end ever crawls backward. That one rule — both ends only move right — is the whole reason a problem that looks quadratic collapses into a single walk.

How Sliding Window Works

Keep a window [left, right] and a running total of the values inside it. Walk right from the start of the array to the end. Each step does two things.

First, grow: add nums[right] to total. The window just got one cell wider on the right.

Then, while the window qualifies — total >= target — shrink it. Record the current length as a candidate answer, subtract nums[left] from total, and advance left. Keep shrinking as long as the window still clears the target, because a shorter qualifying window is a better answer. The moment total drops below target, stop shrinking and let right grow again.

The cost argument is the payoff. right advances exactly n times across the whole run. left also only advances, removing each element at most once, so it advances at most n times too. Add a value once, remove it once: at most 2n moves total, no matter how the window thrashes in between. That is why the brute-force question — "check every one of the n(n+1)/2 possible subarrays" — turns into a linear sweep. The player's edges advanced counter climbs toward that 2n ceiling and never resets, which is the linear bound made watchable.

This version requires non-negative array values and a positive target. Growing the window cannot decrease the sum, and shrinking it cannot increase the sum. A negative value can break that monotonicity: the greedy shrink may stop at the wrong place and miss a shorter valid window. More on that below — it is the single mistake that bites hardest.

Sliding Window Step by Step

The default input is nums = [2, 3, 1, 2, 4, 3] with target = 7. Start with left = 0, total = 0, and the best length still undefined.

1. right = 0: add 2. Window [0, 0], total = 2. 2 < 7, too small — grow again.
2. right = 1: add 3. Window [0, 1], total = 5. Still under 7 — grow.
3. right = 2: add 1. Window [0, 2], total = 6. Still under 7 — grow.
4. right = 3: add 2. Window [0, 3], total = 8. Now 8 >= 7 — valid, length 4. That is the first answer: best = 4. Shrink: drop nums[0] = 2, total = 6, left = 1. 6 < 7, so stop shrinking and grow.
5. right = 4: add 4. Window [1, 4], total = 10. Valid, length 4 — no better than 4, so best stays 4. Shrink: drop nums[1] = 3, total = 7, left = 2. Still 7 >= 7: window [2, 4], length 3 — best = 3. Shrink again: drop nums[2] = 1, total = 6, left = 3. 6 < 7, stop and grow.
6. right = 5: add 3. Window [3, 5], total = 9. Valid, length 3 — ties, best stays 3. Shrink: drop nums[3] = 2, total = 7, left = 4. Still 7 >= 7: window [4, 5], length 2 — best = 2. Shrink again: drop nums[4] = 4, total = 3, left = 5. 3 < 7, stop.

right has reached the end of the array, so the sweep is done. The shortest subarray summing to at least 7 is [4, 3] at indices 4 and 5 — length 2. It took 11 edge moves; brute force would have weighed all 6 · 7 / 2 = 21 possible subarrays.

On the canvas, the box drawn around the window is the inchworm: it stretches rightward when right grows and cinches in from the left when left shrinks, while the running sum above it flips from amber to green the instant the window qualifies. The shortest valid window so far readout ticks down 4 → 3 → 2 as the window tightens — that descent is the entire algorithm, watched live.

Time and Space Complexity

Every case is linear, which is the headline. The window can grow and shrink many times, but the time complexity is governed by the total edge motion, and that is capped at 2n — left and right each cross the array at most once. Space is O(1): two indices and a running sum, no auxiliary structure.

The catch lives in the precondition, not the bound. This variable-size window is correct only for non-negative values; if the array can hold negatives, the greedy shrink breaks and you need a different tool — prefix sums plus a monotonic deque (the harder "shortest subarray with sum at least K" problem, LeetCode #862), which restores O(n) time at the cost of O(n) space. And not every "sliding window" problem is variable-size — the fixed-size variant, where the window stays a constant width and slides one cell at a time, is a simpler cousin that swaps one value in and one out per step.

Edge Cases

• A single cell already reaches the target. The window grows to include it, qualifies, and shrinks straight down to length 1 — the smallest answer possible.
• No subarray ever reaches the target. The sum never crosses the threshold, so the window never shrinks; best stays undefined and the function returns 0.
• The whole array is the only valid window. When even the full array barely clears the target, the window grows to span everything and any shrink drops it below — best equals n.
• Empty array. The loop never runs; return 0.
• Duplicates and equal values. They behave like any other values; the window neither knows nor cares whether two cells hold the same number.

Common Mistakes

• Running it on data that can go negative. This is the one that bites. The shrink loop assumes that dropping a value lowers the sum, so once the window slips below target it stops. A negative breaks that: removing it raises the sum, which means a shorter valid window can be sitting just to the right, unreached. The player ships this as a scenario — load Has a negative and watch [3, -2, 5] with target 4 report length 3 when [5] alone (length 1) already clears it. Non-negative input is not a suggestion.
• Using if where you need while. A single valid window often shrinks several times in a row before it stops qualifying. Replace the while total >= target with an if and you remove at most one cell per grow, so a window that needed several shrinks never fully tightens and your "shortest" can come out too long — on the default [2, 3, 1, 2, 4, 3] with target 7, the if version reports 4 instead of 2.
• Recording the length after shrinking instead of before. The candidate answer is the length of the window while it still qualifies. Subtract nums[left] first and you measure a window that may have already fallen below target, recording a length that was never valid.
• Letting a pointer move backward. The entire O(n) argument rests on both ends advancing monotonically. Reset left to 0 on each new right, or re-add a value you already dropped, and you are back to the O(n²) brute force with extra steps.
• Reaching for the variable-size window when the size is fixed. If the problem asks about every window of a fixed width k, you do not grow and shrink — you slide a constant-width window, adding the entering value and subtracting the leaving one. Using the qualify-and-shrink machinery there is solving a simpler problem the hard way.