Sliding Window Technique

Many array and string problems ask the same question in different costumes: among all contiguous sub-segments of length / weight / property X, which is best? The brute-force answer is to enumerate every interval $[l, r]$ and inspect it — an instant $O(n^2)$ or$O(n^2 \cdot k)$ blow-up that fails the moment$n$ hits a few thousand. The sliding window technique replaces that quadratic with a single linear pass by exploiting one observation: as the right endpoint moves forward, the left endpoint never has to move backward. Two monotone pointers, total work$O(n)$, and a state object that updates incrementally as the window slides.

Sliding window is the workhorse behind moving-average filters in digital signal processing, rate limiters in distributed systems, rolling RMS in audio, k-mer scanning in genomics, time-windowed analytics on infinite streams, and a sizeable fraction of the array and string questions you will be asked in interviews. By the end of this section you will recognize when the technique applies, when it does not, and you will have written it from the universal template six times in two languages.

The Core Idea: A Window That Walks

Define a window as a contiguous range$A[l \,..\, r]$ with$l \le r$ (or the empty window when$r < l$). A summary $S$ of the window — its sum, its character histogram, its set of distinct elements, its maximum — is what we care about. The technique rests on three operations:

1. Add: extend by one on the right,$S \leftarrow S \oplus A[r{+}1]$. Cost is typically $O(1)$.
2. Remove: shrink by one on the left,$S \leftarrow S \ominus A[l]$. Cost is typically $O(1)$.
3. Query: read the current answer from$S$ in $O(1)$.

If your problem can be modeled this way, sliding window applies. Concrete summaries:

Mental model. Think of the window as a centipede crawling along the array. Its head $r$ probes forward; its tail $l$ follows. Neither head nor tail ever reverses. The summary $S$ is what the centipede remembers about the food it has eaten so far.

Why It Is O(n): The Amortized Argument

At first glance the variable-size window looks suspect: an iteration of the outer loop can run an arbitrarily long inner loop that pushes$l$ forward many steps. Could the worst case be $O(n^2)$?

No — and the proof is the textbook example of aggregate amortized analysis. Charge the algorithm for each pointer move:

1. The right pointer $r$ advances exactly once per outer loop iteration. Total moves of$r$: at most $n$.
2. The left pointer $l$ only ever increases (it never decreases). It is bounded above by$n$. Total moves of$l$ across the whole algorithm: at most$n$.
3. Per-move cost is $O(1)$ for sums, hashmap updates, and deque operations.

Total: $O(n) + O(n) = O(n)$. The fact that sometimes the inner loop fires hard and sometimes it does not is irrelevant to the aggregate bound — we paid for each pointer move at most once.

Fixed-Size Window: Moving Sums and Averages

The simplest sliding window has a fixed length$k$. Compute the sum (or any associative aggregate) of $A[0\,..\,k{-}1]$, then update in $O(1)$ as the window steps forward:

$\text{sum}_{r+1} = \text{sum}_r - A[l] + A[r+1]$

Total work: one prime of size $k$ plus$n - k$ constant-time updates —$O(n)$. The naive nested-loop version is $O(n \cdot k)$; for$k = 1000$ on a 10M-sample audio buffer that is the difference between 10 milliseconds and 10 seconds.

1def max_sum_window(arr, k):
2    """Maximum sum of any contiguous length-k subarray. O(n) time."""
3    if k <= 0 or k > len(arr):
4        return None
5    s = sum(arr[:k])               # prime: O(k)
6    best = s
7    for r in range(k, len(arr)):   # slide: O(n - k)
8        s += arr[r] - arr[r - k]   # one add, one subtract
9        best = max(best, s)
10    return best

Variable-Size Window: Grow Then Shrink

Many problems do not pre-fix the window's length. Instead they ask for the longest (or shortest) window satisfying some predicate$P(S)$. The pattern is always:

1. Grow the window on the right by adding$A[r]$ to the summary.
2. While the predicate is violated (or, for "at-most" style problems, would be violated), shrink from the left by removing $A[l]$.
3. Once the window is valid, record the candidate answer.

For this pattern to work the predicate must be monotone in the window: if a window$[l, r]$ is invalid, then every superset with the same $l$ is also invalid (so we have to move $l$); equivalently, removing elements cannot turn a valid window into an invalid one (so we never need to rewind). When this monotonicity fails, sliding window does not apply — see the decision section.

Longest Substring Without Repeating Characters

Given a string $s$, return the length of its longest substring that contains no repeated characters. A naive scan of every $(l, r)$ pair is$O(n^2)$ tries times an$O(n)$ validity check — $O(n^3)$. With sliding window plus a last-seen hashmap, $O(n)$:

s = "abcabcbb"  →  last_seen starts as {}

iterations on "abcabcbb":
r=0 c=a → r=1 c=b → r=2 c=c → r=3 c=a (DUP!) → r=4 c=b (DUP) → ...

r=3, c="a", last_seen["a"]=0, l=0 → 0 ≥ 0 ✓ → duplicate inside window

r=3, c="a", last_seen["a"]=0 → l = 1. Window becomes s[1..3] = "bca", clean.

After r=3: last_seen = {"a":3, "b":1, "c":2}

r=2, l=0 → length 3, best becomes 3 (window "abc")
r=3, l=1 → length 3, best stays 3
r=4, l=2 → length 3, best stays 3

longest_substring_without_repeats("abcabcbb") = 3  ("abc")

1def longest_substring_without_repeats(s: str) -> int:
2    last_seen = {}                  # char -> most recent index in s
3    l = 0                           # left edge of window (inclusive)
4    best = 0                        # length of best window found so far
5    for r, c in enumerate(s):       # r is the right edge, c = s[r]
6        if c in last_seen and last_seen[c] >= l:
7            l = last_seen[c] + 1    # jump l past the duplicate
8        last_seen[c] = r            # record / overwrite latest position
9        best = max(best, r - l + 1) # update best with current window length
10    return best

Trace on $s = \texttt{"abcabcbb"}$:

Minimum Window Substring

Given strings $s$ and $t$, return the shortest contiguous substring of $s$ that contains every character of $t$ with full multiplicity. The classic FAANG question; a beautiful illustration of the grow-then-shrink pattern with two-tier bookkeeping (a per-character debt vector plus an aggregate "missing" counter).

t = "ABC" → need = {A:1, B:1, C:1}
t = "AABC" → need = {A:2, B:1, C:1}

t = "ABC" → missing = 3

s = "ADOBECODEBANC"  →  r = 0,1,2,...,12

r=3, c="B", need={A:0, B:1, C:1}, missing=2 → branch taken, missing → 1

r=4, c="E" (not in t): need["E"]: 0 → -1. No effect on missing.

window = s[0..5] = "ADOBEC", length 6 → first valid → best_len=6, best=(0,5)

l=0, lc="A": need["A"]: 0 → 1.

need["A"] becomes 1 (positive) → missing: 0 → 1, loop will exit.

s="ADOBECODEBANC", t="ABC" → best=(9,12) → return "BANC"

1from collections import Counter
2
3def min_window_substring(s: str, t: str) -> str:
4    if not s or not t:
5        return ""
6    need = Counter(t)            # required count for each char of t
7    missing = len(t)             # total chars still needed (with multiplicity)
8    l = 0                        # left edge
9    best_l, best_r = 0, -1       # best window so far; -1 means none yet
10    best_len = float("inf")
11    for r, c in enumerate(s):
12        if need[c] > 0:          # c is a useful char (still owed)
13            missing -= 1
14        need[c] -= 1             # debt for c goes down (may go negative)
15        while missing == 0:      # window covers all of t — try to shrink
16            if r - l + 1 < best_len:
17                best_len = r - l + 1
18                best_l, best_r = l, r
19            lc = s[l]
20            need[lc] += 1        # we are about to release s[l]
21            if need[lc] > 0:     # released a char we actually needed
22                missing += 1
23            l += 1
24    return s[best_l:best_r + 1] if best_r >= 0 else ""

Trace on $s = \texttt{"ADOBECODEBANC"}$,$t = \texttt{"ABC"}$: the algorithm expands$r$ until index 5 (covering one$A$, $B$,$C$), shrinks to the candidate$\texttt{ADOBEC}$ (length 6), keeps scanning, finds another valid window at index 10 ($\texttt{CODEBA}$, also length 6 after shrinking), and finally at $r = 12$ picks up a fresh $C$ and shrinks all the way to$\texttt{BANC}$ (length 4). That is the winner.

The two-tier bookkeeping trick. Per-character debts plus an integer $\texttt{missing}$ let us check validity in $O(1)$. Without$\texttt{missing}$ we would need to scan the debt dictionary every step — correct, but$O(n \cdot |\Sigma|)$ instead of$O(n + |\Sigma|)$. For 1M-character DNA sequences with the alphabet$\{A, C, G, T\}$ the difference is small; for full Unicode it is enormous.

Longest Subarray With Sum at Most K

Given an array of positive integers$A$ and an integer$K$, return the length of the longest contiguous subarray whose sum is at most$K$. Grow on the right; while the running sum exceeds $K$, shrink on the left:

1def longest_sum_at_most(arr, K):
2    """Longest contiguous window with sum <= K. arr must be NON-NEGATIVE."""
3    s, l, best = 0, 0, 0
4    for r in range(len(arr)):
5        s += arr[r]                  # add right
6        while s > K and l <= r:      # shrink while invalid
7            s -= arr[l]
8            l += 1
9        best = max(best, r - l + 1)  # record
10    return best

Sliding Window Maximum (Monotonic Deque)

Given $A$ and a window size$k$, output an array$M$ with $M[i] = \max(A[i \,..\, i+k-1])$ for$i = 0, \dots, n-k$. Naive: per-window scan of $k$ elements,$O(n \cdot k)$. A heap solution shaves it to$O(n \log k)$ but requires lazy deletion. A monotonic deque nails it at$O(n)$.

The deque stores indices whose values are strictly decreasing. The head is therefore always the argmax of the current window. Two invariants maintain this:

1. When a new index $r$ arrives, pop tail indices whose values are $\le A[r]$: they are dominated by a younger, larger element and can never be a future maximum.
2. When the window has slid past the head index (head$\le r - k$), evict it.

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:
at r=2 the deque holds [1, 2] → values [3, -1] (decreasing).

k=3, r=3 → window is [1..3]. If dq[0]=0, then 0 ≤ 3 − 3 = 0 ✓ → shift it out.

nums=[1,3,-1,...], k=3:
at r=1, nums[r]=3, deque had [0] with nums[0]=1.
1 ≤ 3 → pop. Then push r=1. deque=[1].

nums=[1,3,-1,-3,5,3,6,7], k=3:
r=2 → dq=[1,2] (values 3,-1) → push 3.
r=3 → dq=[1,2,3] (3,-1,-3) → push 3.
r=4 → all popped, dq=[4] (5) → push 5. ...

1function slidingWindowMax(nums: number[], k: number): number[] {
2  const dq: number[] = [];           // indices, values strictly decreasing
3  const out: number[] = [];
4  for (let r = 0; r < nums.length; r++) {
5    // 1. Drop indices that have fallen off the left of the window.
6    while (dq.length > 0 && dq[0] <= r - k) dq.shift();
7    // 2. Drop tail indices whose values are <= nums[r] (they can never win).
8    while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[r]) dq.pop();
9    // 3. Append current index.
10    dq.push(r);
11    // 4. Once we have a full window, the head of dq is its maximum.
12    if (r >= k - 1) out.push(nums[dq[0]]);
13  }
14  return out;
15}

Trace on $A = [1, 3, -1, -3, 5, 3, 6, 7]$ with $k = 3$:

Output: $[3, 3, 5, 5, 6, 7]$. Each index is pushed once and popped at most once across the whole run — the total work for the inner while loops is bounded by$n$, so the algorithm is$O(n)$ in aggregate.

Permutation in a String

Does $s_2$ contain any permutation of$s_1$ as a contiguous substring? Equivalent to: is there an $l$ such that the character frequency of $s_2[l\,..\,l + |s_1| - 1]$ equals the frequency of $s_1$? Fixed-size window of length $|s_1|$; maintain a per-character difference vector$D[c] = \text{freq}_{\text{win}}(c) - \text{freq}_{s_1}(c)$. The window is a match exactly when$D \equiv 0$. To avoid scanning$D$ every step, also maintain a counter$\texttt{matches}$ = number of characters for which $D[c] = 0$. Each window step changes $D$ in two slots, so$\texttt{matches}$ updates in$O(1)$. The answer is yes iff$\texttt{matches} = |\Sigma|$ at any step.

1def has_permutation(s1, s2):
2    if len(s1) > len(s2):
3        return False
4    need = [0] * 26
5    have = [0] * 26
6    for c in s1:
7        need[ord(c) - ord('a')] += 1
8    matches = sum(1 for i in range(26) if need[i] == have[i])
9    for r, c in enumerate(s2):
10        i = ord(c) - ord('a')
11        have[i] += 1
12        if have[i] == need[i]:
13            matches += 1
14        elif have[i] - 1 == need[i]:   # we just unmatched
15            matches -= 1
16        if r >= len(s1):                # window now too big — shrink left
17            j = ord(s2[r - len(s1)]) - ord('a')
18            have[j] -= 1
19            if have[j] == need[j]:
20                matches += 1
21            elif have[j] + 1 == need[j]:
22                matches -= 1
23        if matches == 26:
24            return True
25    return False

The Universal Sliding-Window Template

Every sliding-window problem in this section is an instance of the same loop. Memorize this skeleton; the only thing that changes between problems is the choice of summary$S$ and the predicate$\texttt{valid}$.

1def sliding_window_template(A):
2    l = 0
3    S = init_state()           # e.g. running sum, Counter, deque, ...
4    best = init_best()
5    for r in range(len(A)):
6        S = add(S, A[r])       # extend window to include A[r]
7        while not valid(S):    # tighten until invariant holds
8            S = remove(S, A[l])
9            l += 1
10        best = update(best, l, r, S)
11    return best

1. add / remove must be O(1) amortized for the whole template to be $O(n)$. Hashmap counts, running sums, and monotonic deques satisfy this; sorted-set insertion ($O(\log n)$) bumps the total to$O(n \log n)$, which is still fine.
2. valid must be monotone: if removing elements from a valid window keeps it valid (or vacuously so), we are safe to shrink without rewinding.
3. update is O(1): read off the current best from$r - l + 1$ and / or$S$.
4. For at-most problems (longest sub-window with sum ≤ K, with at most k distinct, etc.) shrink while$\texttt{not valid}$ and record after the inner loop. For at-least problems (shortest sub-window covering all of t, etc.) shrink while$\texttt{valid}$ and record inside the inner loop.

Interactive: The Sliding Window Lab

Pick a problem, edit the inputs, and step the window forward manually or hit Run for auto-play. Green cells are the current window; the blue l arrow and red r arrow mark the boundaries. Watch the "Internal state" panel update as $S$ changes — you can literally see the algorithm's memory.

Real-World Applications

Sliding windows are everywhere outside of interview questions; the technique is the algorithmic fabric beneath whole engineering domains:

Pitfalls and Common Bugs

• Inclusive vs exclusive bounds. Decide once, at the top: is the window $A[l\,..\,r]$ (both inclusive, length $r - l + 1$) or$A[l\,..\,r)$ (right-exclusive, length $r - l$)? Mixing the two within one function is a classic off-by-one factory.
• Forgetting to tighten. If your while-loop is if instead of while, the window can contract by only one step per iteration and you may miss valid configurations — or worse, leave the invariant violated and silently emit a wrong answer.
• Hashmap leftovers. When the window slides off a character, decrement (or delete) its entry in the summary. Stale counts produce ghosts — the dictionary remembers characters that are no longer in the window and the predicate fires falsely.
• Negative or zero values in "sum at most K" or "product at most K" problems break monotonicity. Check the input domain explicitly. AC-coupled sensor data, log-returns on stock prices, and signed deltas are common real-world instances where this bites.
• Empty-window edge cases. If$r$ can fall behind$l$ (it should not, in the canonical template), your add / remove logic must handle the empty window cleanly. Most bugs here come from initializing$r$ before the first iteration and then double-counting on the first add.
• Counting answers vs lengths. "Number of subarrays with sum at most K" is the cumulative sum of$r - l + 1$ over all$r$ — not just the maximum. Easy to confuse with "longest subarray with sum at most K."

When Sliding Window Does Not Apply

Sliding window's linear-time guarantee depends on the non-rewinding property of $l$. When validity is not monotone, that property fails. The replacement-of-choice depends on which monotonicity is violated:

1. Identify the summary $S$ and predicate $P(S)$.
2. Check: if $P([l, r])$ holds, does$P([l+1, r])$ hold? (Monotone shrinkage.)
3. Check: are add / remove both$O(1)$ amortized?
4. If both yes ⇒ sliding window. Plug into the template.
5. If no ⇒ reach for prefix sums + hashmap, monotonic deques, balanced BSTs, or two-heap medians. Each pattern has a chapter ahead.

Sliding window is the first "design pattern" of array algorithms: a small, reusable mental machine that turns$O(n^2)$ brute force into clean$O(n)$ code. Everything else in this chapter — two pointers, prefix sums, dynamic arrays — will keep cross-referencing it. Master the template now, and three chapters from now monotonic stacks and deques (Ch 7) will feel like minor variations on this same theme.