Sliding window

Try it: Longest substring without repeating characters (LC 3)

Watch the window grow and shrink. The right edge moves forward each step; when a duplicate would enter, the left edge advances until the duplicate leaves the window.

1 · Why sliding window matters: the intuition

Brute force over every contiguous subarray is O(n²): pick a start, pick an end, examine the window. Sliding window is the observation that those O(n²) windows overlap heavily. Most of the work you'd repeat is already captured in the previous window's state. The pattern says: maintain that state across iterations, and amortise the work down to O(n) total.

The whole trick lives in one word: incremental. When the right edge moves from index r to r+1, you do constant work to fold the new element into the window's state (a sum, a counter, a frequency map). When the left edge moves from l to l+1, you do constant work to remove the old element. The inner loop that "shrinks until valid" looks scary, but each element is added exactly once and removed at most once across the whole run. So the inner loop's total work over all outer iterations is bounded by 2n, not by n × k.

The invariant is the heart of every sliding-window solution. State it in one sentence before you write code: "the window s[l..r] always satisfies X". Then everything else falls out. Right edge advances unconditionally each step (so the algorithm runs to completion). Left edge advances exactly when adding the new element would break X (so the invariant is preserved). You record the answer when the window is in a valid state. The only subtle question is whether "valid" means before or after the shrink.

2 · How to recognise it: five distinct shapes

Sliding window is the right pattern when the problem asks about a contiguous subarray or substring meeting some constraint. The signals are universal, but the shape of the window splits into five distinct sub-patterns. Naming the shape early saves you from writing the wrong template.

• "Subarray", "substring", "contiguous". The contiguity is the signal. Non-contiguous → think DP or hash map; contiguous → think sliding window.
• "Longest", "shortest", "max sum", "min length". An optimisation over windows.
• "At most K", "exactly K", "no duplicates". A constraint the window must satisfy.
• Fixed window size given. "Subarray of length k": an explicit fixed window. The simplest case.
• Brute force is O(n × k) over windows. Sliding-window almost always reduces this to O(n).
• The input is monotonic in some sense. Adding elements monotonically grows a quantity (sum, count); removing monotonically shrinks it. That monotonicity is what lets the window only-move-forward.

Shape A: fixed-size window

The window's length k is given. Both pointers move in lockstep; no shrink loop. State (sum, count, frequency map) is updated by adding nums[r] and removing nums[r-k] each step. Examples: LC 643 max average of size k, LC 1456 vowels in substring of length k. The template is the simplest of the five.

Shape B: variable-size window with monotone shrink/expand

Right edge advances every step; left edge advances inside a while loop when the invariant breaks. The invariant is monotone: adding an element can only worsen the window's "badness", removing one can only improve it. Classic examples: LC 3 (no repeating chars), LC 209 (sum ≥ target), LC 1004 (at most K zeros). This is the workhorse shape. Write this template into muscle memory first.

Shape C: at-most-K constraint

A specialisation of Shape B where the invariant is literally "the window has at most K distinct things": distinct characters, distinct integers, zeros, replacements. The state is a frequency map plus a counter of "distinct keys with positive count". Shrink while the counter exceeds K. Examples: LC 340 longest substring with at most K distinct chars, LC 904 fruit into baskets, LC 1004 max consecutive ones III.

Shape D: exactly-K via at-most(K) − at-most(K−1)

A trick that converts a hard "exactly" problem into the difference of two easy "at most" problems. The reasoning: any window with exactly K distinct things is counted by at-most-K but not by at-most-(K−1). Subtract and you get exactly. This collapses LC 992 (Subarrays with K Different Integers) and LC 930 (Binary Subarrays With Sum), both otherwise nasty, into two clean Shape-C passes.

Shape E: substring frequency match

Fixed-size window where you track a frequency map and ask "does the current window match the pattern's frequency map?". The window size equals the pattern length. Maintain a matched counter so the per-step check is O(1), not O(Σ). Examples: LC 438 find all anagrams, LC 567 permutation in string. Sub-pattern of Shape A with extra bookkeeping.

3 · Sister algorithms

Sliding window sits inside a family of "monotone pointer-walk" patterns. Knowing the neighbours stops you from misclassifying, and tells you what to reach for when the window itself isn't quite the right shape.

• Two pointers (strict generalisation). Sliding window is the same-direction variant of two pointers (both pointers monotonically advance). The opposite-direction variant (pointers starting at the two ends, walking toward each other) handles "sum equals target on sorted array" (LC 167), "trap rain water" (LC 42), "container with most water" (LC 11). Every sliding-window problem is a two-pointer problem; the converse isn't true.
• Monotonic deque. When you need the max or min inside each window in O(1) amortised. The deque stores indices whose values form a strictly monotone sequence; the front is always the current extremum. Sliding-window-maximum (LC 239) is the canonical use; LC 1438 "Longest Subarray with abs diff ≤ limit" composes a sliding window with two monotonic deques (one for max, one for min).
• Mo's algorithm (offline range query batching). When you have many range queries on a static array and can sort the queries cleverly, you can sweep a sliding window across all of them in O((n + q)·√n). Useful when the per-element add/remove is cheap (counting, frequency) but you have 10⁵ queries. Not a coding-interview pattern, but worth knowing exists for competitive programming and offline analytics.
• Prefix sum + hash map. Not a window, but the right pattern when the "monotone accumulation" assumption breaks. This typically happens because the array can contain negative numbers and "sum exceeds K" is no longer monotone in the window's growth (LC 560). The shape of the solution is "look up the complementary prefix sum in a hash map", not "advance a left pointer".
• Segment tree / Fenwick tree. When the per-element update is O(log n) (range sum, range max with updates), sliding window degrades to O(n log n). Often a better fit when the underlying data is changing too, not just the window.

4 · Canonical example: Longest substring without repeats (LC 3)

Problem. Given a string, find the length of the longest substring without repeating characters.

Input:  "abcabcbb"
Output: 3
Explanation: "abc" is the longest unique-character substring.

Why sliding window

• Brute force: enumerate every substring (O(n²)) and check uniqueness (O(n)) → O(n³).
• Slightly better: enumerate substrings, use a set during the inner loop → O(n²).
• Sliding window: each character enters once, leaves at most once → O(n) amortised.

The invariant

At every step, the window s[l..r] contains only unique characters. When a new character at r+1 would duplicate one already in the window, advance l until the duplicate is gone.

Build the intuition: answer first

• What does the window contain at every step? Articulate the invariant: the substring s[l..r] always has unique characters.
• When does the right edge advance? Every iteration of the outer loop; that's how we cover the input.
• When does the left edge advance, and how far? Only when adding s[r] would break the invariant. How do you "fix" the invariant? What's the smallest move that restores it?
• When do you update best? After the window is valid (the right edge has been added). Why not inside the shrink loop?
• Why is this O(n) and not O(n²)? Count the total moves of the left edge across the whole run.

Go scaffold: fill in the shrink-then-add steps

func lengthOfLongestSubstring(s string) int {
    seen := make(map[byte]bool)
    l, best := 0, 0

    for r := 0; r < len(s); r++ {
        // SHRINK: while s[r] is already in the window, advance l
        for /* TODO: condition */ {
            // TODO: what do you remove from seen?
            // TODO: advance l
        }

        // EXPAND: now safe to add s[r] to the window
        // TODO: add s[r] to seen

        // UPDATE: window length is r - l + 1
        // TODO: update best
    }

    return best
}

5 · Five-problem progression

Solve in order. Each step adds a wrinkle. Time-box at 25 minutes; if stuck past 20, peek at the pattern.

6 · Fixed-window variant: try it

When the window size is given, both pointers move in lockstep. No while-loop; just maintain a running aggregate as the right edge enters and the left edge exits. Watch the green "added" cell and red "dropped" cell each step:

Build the intuition: fixed window

• The init step is special. Before the slide loop, you need the sum of the first window. Why isn't that part of the slide loop?
• What does each slide step do? Two operations of equal weight: add the new right element, drop the old left element. Both are O(1).
• How many slides? Exactly n - k. Add the init window and you have n - k + 1 windows total: the count of length-k contiguous subarrays.
• The rookie mistake. Recomputing sum(window) on every slide. That's O(n × k); the whole point is incremental update.

Go scaffold: slide template

func maxSumWindow(nums []int, k int) int {
    if len(nums) < k {
        return 0
    }

    // INIT: sum of nums[0..k-1]
    sum := 0
    // TODO: prime the window

    best := sum

    // SLIDE: each step adds nums[r], drops nums[r-k]
    for r := k; r < len(nums); r++ {
        // TODO: incrementally update sum
        // TODO: update best
    }

    return best
}

The structure is the same idea (each element enters and leaves once), but the bookkeeping is simpler because the window is always size k. Many "average / sum / count over k consecutive items" problems collapse to this template.

Fixed-window family

• Max average of size k. LC 643. Same template, divide by k at the end.
• Number of substrings of size k with k distinct chars. LC 1456 / LC 1876. Track a frequency map, increment/decrement as the window slides.
• Find all anagrams of pattern in text. LC 438. Two frequency arrays of size 26; compare for equality each slide. O(n × 26) which is just O(n) with a constant.
• Permutation in string. LC 567. Same shape as above; ask "is the current window's frequency map equal to the pattern's?".
• Sliding window median. LC 480. Hardest of the family: needs an order-statistic structure (two heaps or sorted multiset).

7 · Variable-window deep dive: Min Window Substring (LC 76)

LC 76 is the definitive variable-window problem and the one most candidates fail. Given a string s and pattern t, find the shortest substring of s that contains every character of t (with at least the right multiplicity).

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The shortest substring of s containing A, B, and C is "BANC".

The "have / need" trick

Two character-count maps: need built from t, have tracking the current window. Plus a counter matched = number of characters where have[c] >= need[c]. When matched equals len(need), the window covers t.

Build the intuition: answer four questions before coding

1. What does matched represent, and why an integer? The number of distinct characters c where have[c] ≥ need[c]. Updating an integer is O(1); checking "does have cover need" by full-map equality would be O(alphabet) per step.
2. When does matched increase? Only at the moment have[c] first reaches need[c], not on every increment. Why?
3. When does matched decrease? Only at the moment have[c] first drops below need[c], not on every decrement. Why?
4. Inside the shrink loop, what order matters? Update best first, then shrink — or the other way? Hint: at the top of the shrink loop the window is still valid; at the bottom it may not be.

Go scaffold: the "have / need" template

func minWindow(s, t string) string {
    if len(s) == 0 || len(t) == 0 {
        return ""
    }

    need := map[byte]int{}
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
    have := map[byte]int{}
    required := len(need)
    matched := 0

    l := 0
    bestL, bestLen := 0, -1

    for r := 0; r < len(s); r++ {
        c := s[r]
        // EXPAND
        have[c]++
        // TODO: when does matched increase?

        // SHRINK while window is valid
        for matched == required {
            // TODO: update bestL / bestLen if window is smaller than current best

            lc := s[l]
            have[lc]--
            // TODO: when does matched decrease?
            l++
        }
    }

    if bestLen == -1 {
        return ""
    }
    return s[bestL : bestL+bestLen]
}

Trace through s = "ADOBEC", t = "ABC"

Continuing past index 5 in the full string, the algorithm finds "BANC" (length 4): the answer.

8 · The monotonic-deque variant: Sliding Window Maximum (LC 239)

LC 239 asks for the maximum of every length-k window. The naive O(n × k) recomputes max per window. The trick is a monotonic deque that maintains a strictly decreasing sequence of indices: the front is always the current maximum.

The two pop rules

Two rules govern when an index is removed:

• Pop from the front if its index has fallen out of the window (front_idx ≤ r - k). At most one pop per step.
• Pop from the back while the new value is greater-or-equal to the back's value. Multiple pops possible per step, but each index is popped at most once total, so amortised O(1).

Build the intuition: three claims to convince yourself of

• Why store indices, not values? We need to know when an entry "falls out" of the window; that's a position-based question. From an index we can recover the value; from a value we can't recover the position.
• Why "strictly decreasing"? If indices i < j have nums[i] ≤ nums[j], then i is forever dominated: any future window containing i also contains j, and j is bigger. So drop i.
• Why is the back-pop loop amortised O(1)? Each index is pushed exactly once across the whole walk. Each can be popped at most once. So total push + pop ≤ 2n. The inner loop's total work is bounded by total pushes, not by step count.

Go scaffold: monotonic-deque shape

func maxSlidingWindow(nums []int, k int) []int {
    // Deque holds INDICES; nums at those indices are strictly decreasing front→back
    dq := []int{}
    out := []int{}

    for i := 0; i < len(nums); i++ {
        // RULE 1 — drop the front if its index is out of the window
        // TODO: pop front while dq[0] <= i - k

        // RULE 2 — maintain the strictly-decreasing invariant
        // TODO: pop the back while nums[dq[back]] <= nums[i]

        // PUSH the current index
        dq = append(dq, i)

        // EMIT the max once the window is filled
        if i >= k-1 {
            // TODO: append nums[dq[0]] to out
        }
    }

    return out
}

9 · Three more worked problems

Three problems, three different shapes from Section 2. Solve each one from the template before reading the walkthrough. The muscle memory is worth more than the explanation.

9a · LC 209: Minimum Size Subarray Sum (Shape B, minimisation)

Problem. Given an array of positive integers and a target k, return the minimal length of a contiguous subarray whose sum is ≥ k. Return 0 if none exists.

Input:  nums = [2, 3, 1, 2, 4, 3], k = 7
Output: 2
Explanation: [4, 3] is the shortest subarray with sum >= 7.

This is Shape B (variable window, monotone invariant) in its cleanest form. The invariant: the window sum stays ≥ k just barely. Expand right to grow the sum; shrink left while still ≥ k to find the smallest valid window. Record the answer inside the shrink loop; that's the order trap unique to minimisation problems.

func minSubArrayLen(k int, nums []int) int {
    l, sum := 0, 0
    best := len(nums) + 1 // sentinel: larger than any valid window

    for r := 0; r < len(nums); r++ {
        sum += nums[r]

        // SHRINK while window still valid; record inside the loop
        for sum >= k {
            if r-l+1 < best {
                best = r - l + 1
            }
            sum -= nums[l]
            l++
        }
    }

    if best > len(nums) {
        return 0
    }
    return best
}

9b · LC 567: Permutation in String (Shape E, frequency match)

Problem. Given strings s1 and s2, return true iff some permutation of s1 is a substring of s2.

Input:  s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains "ba", which is a permutation of "ab".

Shape E: fixed window of size len(s1), sliding across s2. The window matches when its frequency map equals s1's frequency map. Comparing two 26-element arrays each step is technically O(26), a constant, but the elegant version maintains a matched counter so the per-step check is O(1).

func checkInclusion(s1, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    var need, have [26]int
    for i := 0; i < len(s1); i++ {
        need[s1[i]-'a']++
    }

    matched := 0 // count of letters c where have[c] == need[c]
    for i := 0; i < 26; i++ {
        if need[i] == 0 {
            matched++ // trivially matched
        }
    }

    for r := 0; r < len(s2); r++ {
        c := s2[r] - 'a'
        have[c]++
        if have[c] == need[c] {
            matched++
        } else if have[c] == need[c]+1 {
            matched-- // just overshot
        }

        if r >= len(s1) {
            lc := s2[r-len(s1)] - 'a'
            have[lc]--
            if have[lc] == need[lc] {
                matched++
            } else if have[lc] == need[lc]-1 {
                matched-- // just undershot
            }
        }

        if matched == 26 {
            return true
        }
    }
    return false
}

9c · LC 992 (HARD): Subarrays with K Different Integers

Problem. Given an integer array nums and an integer k, return the number of contiguous subarrays containing exactly k different integers.

Input:  nums = [1, 2, 1, 2, 3], k = 2
Output: 7
Explanation: Subarrays with exactly 2 distinct integers are:
  [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

"Exactly K" is famously harder than "at most K" because the constraint isn't monotone in window growth: adding an element can take a window from "exactly K" to "K+1" or leave it at "exactly K". Shape D is the trick: exactly K = at-most(K) − at-most(K−1). Both halves are clean Shape-C sliding windows.

func subarraysWithKDistinct(nums []int, k int) int {
    return atMost(nums, k) - atMost(nums, k-1)
}

// Count subarrays with at most k distinct integers.
func atMost(nums []int, k int) int {
    count := make(map[int]int)
    distinct, l, total := 0, 0, 0

    for r := 0; r < len(nums); r++ {
        if count[nums[r]] == 0 {
            distinct++
        }
        count[nums[r]]++

        // Shrink while too many distinct
        for distinct > k {
            count[nums[l]]--
            if count[nums[l]] == 0 {
                distinct--
            }
            l++
        }

        // Every window ending at r with size r-l+1 has <= k distinct.
        // It contributes r-l+1 subarrays ending at r.
        total += r - l + 1
    }
    return total
}

10 · How to solve hard sliding-window problems, step-by-step

When you sit down with a problem and you've recognised it's a sliding window, the next ten minutes determine whether you'll get a clean solution or three rounds of debugging. Run this checklist before you touch the keyboard.

Step 1: State the invariant the window maintains

One sentence. "The window nums[l..r] always contains at most K distinct integers". "The window s[l..r] always has only unique characters". "The window's sum is ≥ target". If you can't write this in one sentence, you don't understand the problem yet, and writing code is premature. The invariant is the contract between every iteration; without it, expand and shrink are guessing.

Step 2: Decide what triggers expand vs shrink

Expand is almost always "every iteration of the outer loop": the right edge advances unconditionally. The interesting decision is shrink: it triggers when the invariant breaks. Be explicit about which condition means "invariant broken". For LC 3, it's "duplicate of s[r] is in the window". For LC 209, it's the reverse: the window is too large (sum ≥ target) and we want to find the smallest valid one, so shrink while still valid, not while invalid.

Step 3: Decide when to record the answer

This is where most bugs live. Two rules:

• "Longest" problems. Record after the shrink loop, when the window is valid. The window length is r - l + 1.
• "Shortest" problems. Record inside the shrink loop, at the top, when the window has just become valid (or is still valid) and we want to remember it before shrinking further.

For "count of subarrays" problems (LC 992, LC 713), the answer is incremented by r - l + 1 per outer iteration: one for each valid left endpoint that pairs with this right endpoint.

Step 4: Check if you need the at-most-K trick

If the problem says "exactly K" of something (distinct integers, ones, sum), your shrink condition is non-monotone, and a single sliding-window pass won't work. Convert it: write atMost(k) - atMost(k-1). Both halves are clean Shape-C windows; the subtraction does the "exactly" filtering for free. This single trick converts LC 992, LC 930, LC 1248 from hard to medium-clean.

Step 5: Pick the data structure for the window's state

The window has to maintain enough state to test the invariant in O(1). Match the state to the constraint:

• "No duplicates" → hash set, or a freq map for bounded alphabet.
• "At most K distinct" → freq map + distinct counter.
• "Sum / count" → running integer; add on expand, subtract on shrink.
• "Frequency match against pattern" → two freq maps + matched counter.
• "Max / min in window" → monotonic deque.
• "Median / kth largest in window" → two heaps or sorted multiset (degrades to O(n log k)).

11 · A diagram of expand and shrink

What the window actually does, frame by frame, over the input "abcabcbb" with the LC 3 invariant. Each frame shows whether the expand caused a shrink, and what the window's contents are after.

12 · The decision tree: fixed vs variable vs monotonic

The monotonic-deque branch is the tricky one — most candidates either don't reach for it (and submit O(n × k)) or reach for it inappropriately (when a heap is cleaner). The give-away for monotonic deque: "max of every window" or "min of every window". For "kth largest in each window", use two heaps instead.

13 · Common pitfalls, and the bugs everyone writes once

• Updating best in the wrong place. For a "longest" problem, update after expanding (when the window is valid). For "shortest", update inside the shrink loop (when the window has just become valid). Easy to flip these.
• Forgetting that the inner while is amortised, not nested. A reviewer pointing at a nested loop and saying "this is O(n²)" — explain the amortisation: each character moves left-to-right exactly once.
• Using a hash map when a fixed-size array would do. If the alphabet is bounded (say, 26 lowercase letters), a length-26 array beats a hash map by 5–10× in practice.
• Off-by-one on window size. r - l + 1, not r - l. The +1 catches half the bugs.
• Updating the count map before checking the constraint. Order matters: in "have / need" problems (LC 76), the canonical bug is checking have == need after updating need instead of after updating have.
• Negative numbers in sum-based windows. Sliding window assumes monotonic accumulation. With negative numbers, "sum of subarray exceeds K" is no longer monotonic — reach for prefix-sum + hash map instead.
• Re-computing the aggregate on every step. The whole point is incremental update. sum(window) on every iteration kills the speedup.
• Forgetting to shrink BEFORE recording the answer (shortest problems). On a "shortest" problem, the moment the invariant is freshly true is when you should record. If you advance l first and then record, you record a window that may already be too small to still satisfy the invariant. The canonical bug is "l++; if (valid) best = ..." instead of "if (valid) best = ...; l++".
• Window-state update order bugs. When you remove nums[l], the order matters: decrement have[nums[l]], then check whether matched needs to drop, then advance l. Flipping any two of those three steps produces an off-by-one that shows up only on small adversarial inputs. The fix is to write the three steps as a comment block before coding, and refuse to reorder them.
• The at-most-K off-by-one. atMost(k) - atMost(k-1) is the trick — but with k = 0 it falls apart (atMost(-1) is not meaningful). Guard with if k == 0 { return 0 } or define atMost(-1) = 0 explicitly. Forgetting this crashes on the edge case where the test use includes k=1.
• Incrementing matched on every step (not just the boundary). In Shape E / LC 76, matched should increment only when have[c] first reaches need[c], not every time you add the character. The naive version (increment whenever you add a character that's in need) inflates matched past required and the shrink loop never terminates properly.
• Wrong "while" condition direction. "Shrink while invalid" vs "shrink while valid" depends on whether you're maximising (shrink while invalid to restore validity) or minimising (shrink while valid to find the smallest valid). Conflating these is the most common sliding-window mistake on a whiteboard.

14 · Complexity

Sliding window's O(n) amortised time is the headline. The space depends on what state the window has to track.

15 · Variants & related patterns

• Two pointers. Sliding window is a same-direction two-pointer. The opposite-ends variant is the sister pattern.
• Monotonic stack / deque. Composes with sliding window for "max in each window" — LC 239.
• Hash map. Most variable windows track membership via a hash map or set. Often the "shape" is hash-map-with-window-discipline.
• Prefix sums + hash map. For "subarray with sum K" where the window approach fails (negatives) — LC 560. Different pattern, same problem class.
• Adjacent: data structures cabinet. Reference for arrays, deques, hash sets.

16 · Where this gets asked

17 · Try it yourself

Maximum Average Subarray I · LC 643

Fixed-window warm-up. Sum the first K, slide by subtracting the left and adding the right. Hint: track the running sum as an integer until the end, then divide once — avoids float drift.

Longest Substring Without Repeating Characters · LC 3

Variable-window canon. Expand right; if the new char is in the window, shrink left. Hint: a hashmap of char → last_index lets you jump left directly past duplicates.

Minimum Window Substring · LC 76

Variable-window with a counter. Hint: track a need counter — number of characters still missing — so you don't re-check the whole map every step.

Sliding Window Maximum · LC 239

Monotonic-deque variant. Maintain a deque of indices whose values are strictly decreasing. Hint: every element enters and leaves the deque exactly once — that's the amortised O(1).

Stretch — Subarrays with K Different Integers · LC 992

"Exactly K" = "At most K" − "At most K−1". Two sliding-window passes, subtract. Hint: "exactly" is hard but "at most" is easy — the difference of two easy problems is the hard one.

Further reading

• Skiena — The Algorithm Design Manual. Section 4 on sorting + scanning patterns. Sliding window appears as "the two-pointer pattern with a moving window".
• Sedgewick & Wayne — Algorithms (4th ed). Chapter 1.4 covers running aggregates; chapter 1.3 covers deques.
• Neetcode — Sliding Window playlist. Twelve videos walking the canonical problems. The cleanest free explainers.
• The "monotonic deque" trick. The classic explainer of LC 239 — every entry on Codeforces or LeetCode discuss tagged "sliding-window-maximum" rehashes this. Worth one read.
• Adjacent: the methodology page. Spaced-repetition intervals and the 20-minute rule.
• Adjacent: two pointers. The sister pattern — same-direction is often a sliding window.