---
title: "Sliding Window"
description: "Grow and shrink a window over a sequence to answer subarray questions in O(n)."
source: https://vizlearn.app/algorithms/search/sliding-window
access: premium (interactive player requires Lifetime; this doc is free)
---

# 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

| Case | Time |
|---|---|
| Best (the first cell already clears target) | O(n) |
| Average | O(n) |
| Worst (window has to span most of the array) | O(n) |

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.