Sliding window
AlgorithmsHigh priority~1.5 hA moving sub-range over a sequence — grow the right edge, shrink the left, in one O(n) pass.
Definition
A sliding window maintains a contiguous sub-range [left, right] over an array or string. You extend right to take in more, and advance left to drop elements once the window breaks some invariant. Because each index enters the window once and leaves once, the whole scan is O(n) — even though it reads like a nested loop, the two pointers only ever move forward.
When to use
Reach for a sliding window on a contiguous subarray or substring problem asking for the longest, shortest, or a count satisfying some condition — longest substring without repeats, smallest subarray with sum ≥ target, all anagram start indices. The window is fixed when its size is given outright, and variable when you grow right and shrink left to keep an invariant true. The cue: the answer is a run of adjacent elements, and a brute force would re-scan overlapping runs.
Techniques
Fixed window — the width k is fixed by the prompt. Slide one step at a time: add the entering element, drop the leaving one, and read the answer off the window in O(1) (maximum average subarray of size k, anagram start indices).
Variable window — grow right greedily, then shrink left only while an invariant is broken. How far you shrink is data-dependent, but each index still enters and leaves once, so it stays O(n) (longest substring without repeats, longest repeating-character replacement).
Monotone / non-shrinking window — a variant where left advances at most one step per right, so the window width never decreases and its final width is the answer. Useful when you only care about the largest valid window (character replacement).
Related structures
Window contents and its sibling pattern
A window is a directional variant of the two-pointers scan — both indices move the same way and the span between them is the answer, rather than converging from opposite ends. It is almost always paired with a helper that summarizes what's inside the window in O(1): a set for uniqueness, a count map (or a 26-slot letter array) for frequencies, or a running sum. Choosing that helper — and updating it incrementally as the edges move — is most of the problem.
Implementation
let left = 0;
let best = 0;
for (let right = 0; right < arr.length; right++) {
add(arr[right]); // extend the window rightward
while (invariantBroken()) {
remove(arr[left]); // shrink from the left until valid
left++;
}
best = Math.max(best, right - left + 1); // window is valid here
}Worked examples
Smallest subarray with sum ≥ target — given positive numbers, find the length of the shortest contiguous run whose sum is at least target (here target = 7). Grow right, adding to a running sum. The moment sum >= target, the window is valid — so contract from left, recording the width each time it stays valid, because a shorter qualifying window is always better.
nums = [2, 3, 1, 2, 4, 3], target = 7
First time the window reaches the target: [2,3,1,2] sums to 8. best = 4.
Dropping the 2 breaks the invariant (6 < 7), so stop shrinking and extend again.
[3,1,2,4] = 10 is valid; contracting to [1,2,4] = 7 is still valid at width 3. best = 3.
One more shrink to [2,4] = 6 breaks the invariant, so stop and reach right again.
[4,3] hits exactly 7 — width 2, the smallest valid window. Answer: 2.
function minSubArrayLen(target, nums) {
let left = 0;
let sum = 0;
let best = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right]; // extend the window
while (sum >= target) { // valid — try to make it smaller
best = Math.min(best, right - left + 1);
sum -= nums[left++]; // shrink from the left
}
}
return best === Infinity ? 0 : best;
}Both pointers only move forward, so each element is added and removed at most once — O(n) time and O(1) space. A naïve scan that re-summed every subarray would be O(n²).
Things to look out for
- Recomputing the window's summary from scratch each step reintroduces the O(n²) you came to avoid — update it incrementally as
left/rightmove. - With a count map, shrink fully: advance
leftuntil the offending count actually drops, not just once. - A window's width is
right - left + 1, notright - left— an easy off-by-one. - On a fixed-size window, evict the leaving element every step once the window is full — forgetting it lets the window grow without bound.
Corner cases
- Empty input — return
0/ an empty result before entering the loop. - A pattern or window longer than the input (fixed-size variants) — no valid window exists.
- All-identical or single-element inputs.
- No valid window exists — return the sentinel (
0,-1, or"") the prompt expects.