Sliding WindowAlgorithmaka dynamic window, expand-and-shrink, caterpillar method, two-pointer window

Sliding Window (Variable Size)

Grow a window from the right while a condition holds and shrink it from the left when it breaks, finding the longest or shortest valid contiguous subarray in O(n).

▶ VisualizePattern: Two PointersPractice (4)
Progress

Overview

A variable-size sliding window finds the longest or shortest contiguous subarray satisfying a constraint — sum ≥ s, at most k zeros flipped, no repeated characters, at most k distinct values. Two indices l and r delimit the window; r always moves right to admit a new element, and l moves right only as far as needed to restore the constraint. Both pointers move at most n times, so the total is O(n) even though the inner shrink loop looks nested.

The technique applies when the constraint is monotone with respect to inclusion: if a window is valid, every sub-window is valid (for "longest" problems), or if a window is invalid, every super-window is invalid. Sum of non-negative numbers, count of distinct characters, and count of a specific value are all monotone. Sums with negative numbers are not, and then the window pattern fails — that case belongs to Prefix Sum with a Hash Map or a Monotonic Queue.

contiguoussubarraylongestshortestmonotonicO(n)

Intuition

A mental model before the formal terms.

A caterpillar crawling along a branch: it stretches its head forward as long as the branch can hold it, and when the stretch becomes too much it pulls its tail up. The head never goes backward and the tail never goes backward, so the caterpillar traverses the branch in one trip while trying every stretch length it can support at each position.

For "longest window with at most k distinct letters", imagine a bag that can hold k kinds of letters. Keep tossing in the next letter; the moment there are k + 1 kinds, throw out letters from the oldest end until one kind disappears. The bag was as full as it could legally be at every step, so the biggest bag you ever saw is the answer.

How it works

  1. Initialize l = 0 and an empty aggregate (sum, count, frequency map) describing the window a[l..r].
  2. For each r from 0 to n − 1: add a[r] to the aggregate — the window grows by one on the right.
  3. While the window violates the constraint: remove a[l] from the aggregate and l++. The window shrinks from the left until valid again.
  4. For longest-type problems, the window is now valid: record r − l + 1 if it beats the best.
  5. For shortest-type problems, flip the roles: shrink *while the window is still valid* and record the length just before it stops being valid (or after each successful shrink).
  6. Return the best length (or the window bounds, or the count of valid windows if the problem asks for a count — see interview patterns).

Why it works

Invariant (longest variant): after processing r, the window [l, r] is the *longest valid window ending at r* — i.e. l is the smallest index such that a[l..r] is valid. This holds because monotonicity means validity of a[l..r] implies validity of a[l'..r] for all l' > l, so the valid left endpoints for a fixed r form a suffix [l*, r], and the shrink loop stops exactly at l*.

Why `l` never needs to move backward: when r advances to r + 1, any window a[l'..r+1] with l' < l contains a[l'..r], which was already invalid (that is why l moved past it). By monotonicity the larger window is invalid too. So every left endpoint discarded for r is also useless for r + 1, and no valid answer is ever skipped.

Because the best window ending at each r is examined, the global optimum — which ends at *some* r — is found. l and r each advance at most n times, so the total number of aggregate updates is at most 2n: O(n) time.

If the constraint is not monotone (e.g. sum ≥ s with negative numbers), the valid left endpoints for a fixed r are not a contiguous suffix and the shrink loop can stop too early; the invariant breaks and the answer can be wrong.

Recognition

How to tell a problem wants this.

  • "Longest" or "shortest"/"minimum length" paired with "contiguous", "subarray", or "substring".
  • A capacity-style constraint: "at most `k`" (distinct characters, zeros, replacements, types of fruit), "sum ≥ s", "no repeated characters", "with at most k operations".
  • All values are non-negative (for sum constraints) — a strong hint that the sum is monotone and a window will work; negative values are the hint that it will not.
  • "Count the number of subarrays with…" plus a monotone constraint — the same window, but add r − l + 1 per step instead of taking a max (for "at most"), and use "at most k" minus "at most k − 1" for "exactly k".
  • Constraints n ≤ 10^5 or 10^6 with a brute force that enumerates O(n²) subarrays.
“sorted array” → Two Pointers“contiguous subarray” → Sliding Window

Interactive visualization

Play, step, change the input. ← → and space work too.

2
0
3
1
1
2
2
3
4
4
3
5
1
6
5
7
2
8
1/27Find the shortest subarray with sum ≥ 7. Because all values are positive, growing the window only increases the sum and shrinking only decreases it — that monotonicity makes two pointers valid.
Current windowEntering (r)Shrunk awayBest window
PseudocodeLearn Sliding Window (Variable Size) →
1l = 0, sum = 0, best = ∞
2for r in 0 .. n-1:
3  sum += a[r]
4  while sum >= target:
5    best = min(best, r - l + 1)
6    sum -= a[l]; l += 1
7return best (or 0 if never reached)
Variables
l0
sum0
best∞
target7
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1l = 0, best = 0, state = empty
2for r in 0..n-1:
3  add a[r] to state
4  while state violates constraint:
5    remove a[l] from state
6    l = l + 1
7  best = max(best, r - l + 1)   # window [l, r] is the longest valid one ending at r
8return best

Implementations

1# Max Consecutive Ones III: longest subarray of 1s after flipping at most k zeros
2def longest_ones(a: list[int], k: int) -> int:
31 · Window [l, r] with a count of zeros inside it
4    l = 0
5    zeros = 0
6    best = 0
72 · Expand the window by one on the right
8    for r, x in enumerate(a):
9        if x == 0:
10            zeros += 1
113 · Shrink from the left while the constraint is violated
12        while zeros > k:
13            if a[l] == 0:
14                zeros -= 1
15            l += 1
164 · Window is valid: record its length
17        best = max(best, r - l + 1)
185 · Longest valid window seen
19    return best
Walkthrough
  1. enumerate(a) yields (r, x) so the entering element is read once without a second index expression.
  2. zeros is the whole window state; a Counter would be overkill for a single tracked value.
  3. The while zeros > k loop shrinks from the left, checking a[l] before advancing l.
  4. best = max(best, r - l + 1) records the valid window length.
  5. The function returns an int.
Complexity (this implementation)
time O(n) · space O(1)

Slicing a[l:r + 1] to inspect the window would copy — O(window) per step; the code never slices.

Language notes
  • For "at most k distinct" use collections.Counter or defaultdict(int) for the window, and delete keys when their count hits 0 so len(window) stays the distinct count.
  • enumerate avoids range(len(a)) plus indexing.
  • The inverted shrink (while total >= target) gives the shortest-window template.
Common mistakes in this language
  • Using a[l:r + 1].count(0) inside the loop — O(n^2).
  • Using if instead of while to shrink.
  • Forgetting to update zeros when a[l] leaves.
Language differences that matter here
  • When the window state is a frequency table (the "at most k distinct" family): Python uses Counter/defaultdict, C++ std::unordered_map or a fixed std::array<int,26>, JS/TS Map (object keys would stringify numbers).
  • TypeScript can express the binary precondition as (0 | 1)[]; C++, JS and Python accept any ints and rely on the data.
  • Inspecting the window by slicing (a[l:r+1], a.slice(l, r+1)) copies in Python and JS/TS; C++ iterators or index arithmetic do not — the algorithm should never need the slice.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Each pointer advances at most n times. Space O(k) or O(Σ) when the window state is a frequency map.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Longest/shortest contiguous subarray or substring under a monotone constraint.
  • Counting subarrays satisfying an "at most k" property (sum with non-negative values, distinct elements, occurrences of a value).
  • Constraints expressed as budgets: at most k flips, replacements, or distinct kinds.
  • Any time you catch yourself writing for l: for r: over a contiguous range with a monotone check.
Avoid it when
  • The constraint is not monotone: subarray sum equals k with negative numbers, "exactly k distinct" directly (use the at-most-k minus at-most-k−1 trick), or conditions involving max/min differences that a shrink can *fix* from either side.
  • The problem is about subsequences, not contiguous ranges.
  • Two-dimensional windows over a matrix — combine 2D Prefix Sum with a window over one dimension instead.
  • Very small n where the O(n²) enumeration is clearer and fast enough — but say so explicitly.

Alternatives

Prefix SumSliding Window (Fixed Size)Sliding Window with Frequency MapTwo Pointers (Opposite Ends)Monotonic Queue
Compare: Sliding Window vs Two Pointers

Common mistakes

  • Using if instead of while to shrink — one removal may not restore validity.
  • Updating best before shrinking in a longest-type problem (window may be invalid), or after shrinking in a shortest-type problem (window is now invalid, length is one too short).
  • Applying the window to a sum constraint with negative numbers and getting wrong answers on tests with mixed signs.
  • Forgetting to remove a[l] from the aggregate before incrementing l.
  • For counting "exactly k", trying to count directly inside the loop instead of computing atMost(k) − atMost(k−1).

Interview patterns

  • Longest Substring Without Repeating Characters (window with a last-seen map or a set).
  • Max Consecutive Ones III / Longest Repeating Character Replacement (budget of k changes; the latter uses window − maxFreq ≤ k).
  • Minimum Size Subarray Sum (shortest, positive numbers).
  • Fruit Into Baskets / Longest Substring with At Most K Distinct Characters.
  • Subarrays with K Different Integers via atMost(k) − atMost(k−1); Count Number of Nice Subarrays with the same trick on odd counts.
  • Binary Subarrays With Sum (0/1 array): at-most trick again, or Prefix Sum with a hash map if values can be negative.
Interview questions on this
Mock interviews

Example problems

Longest Substring Without Repeating CharactersmediumMax Consecutive Ones IIImediumLongest Repeating Character ReplacementmediumFruit Into Basketsmedium