λDSA Learning Hubpart of DSA Atlas

Sliding Window

Intermediate~2h · 5 lessons12 practice problems

Maintain a contiguous window and update its state incrementally: fixed-size averages to variable-size 'longest substring' problems, all in O(n).

0 of 5 lessons checked off

Introduction

What it is

  • Sliding window maintains a contiguous range [left, right] over a sequence, together with incrementally-updated state (sum, counts, distinct characters) describing what's inside.
  • Fixed windows slide both edges together (size k given); variable windows expand right greedily and contract left only when a constraint breaks.

Why it matters

  • Recomputing every subarray from scratch costs O(n·k) or O(n²); updating state by ±1 element makes the whole scan O(n).
  • 'Longest/shortest/count of contiguous ___ satisfying ___' is among the most common interview phrasings, and this is its designated tool.

How it works

  • Fixed: seed the first window, then add the entering element and remove the leaving one per step.
  • Variable: for each right, restore validity by advancing left while broken; then record the candidate answer. Both edges only move forward — that one-way motion is the O(n) proof.
  • State must support O(1) add/remove: sums, hash counts, at-most-k trackers. (Max/min in a window needs a monotonic deque — next topic.)

Where it's used

  • Rate limiters (requests in the last minute), moving averages in monitoring, network congestion windows, and plagiarism shingling all maintain sliding state.

In interviews

  • Longest substring without repeating characters, minimum window substring, max sum subarray of size k, longest repeating character replacement, permutation in string, fruit into baskets.
Analogy: A train window moving through a landscape: to know what's visible you don't re-survey the world each second — one scene enters the frame, one leaves, and you adjust your description by exactly those two changes.

Interactive diagram

Add the entering element, subtract the leaving one — two operations replace re-summing the window.

Build the first window of size 3

Sum the first 3 elements once: 8. Re-summing every window from scratch would cost O(n·k); we will slide instead.

sum
8
best
8

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Fixed-size windows

    Seed, then add/remove one element per slide.

    20 min
  2. Variable-size windows

    Expand right, contract left on violation; the while-inside-for shape.

    30 min
  3. Window state with hash counts

    Distinct characters, at-most-k, and frequency matching.

    25 min
  4. Shrinking for minimums

    Minimum window substring: contract while VALID instead of while broken.

    25 min
  5. When windows don't apply

    Negative numbers break sum monotonicity; subsequences aren't contiguous.

    15 min

Operations

Fixed-size window

One subtraction and one addition per slide keep the state exact.

Build the first window of size 3

Sum the first 3 elements once: 8. Re-summing every window from scratch would cost O(n·k); we will slide instead.

sum
8
best
8
def max_sum_window(nums: list[int], k: int) -> int:    """Maximum sum over all length-k windows. O(n)/O(1)."""    if k > len(nums):        raise ValueError("window larger than array")    window = sum(nums[:k])    best = window    for right in range(k, len(nums)):        window += nums[right] - nums[right - k]   # enter, leave        best = max(best, window)    return best
Time: O(n) vs O(n·k) recomputingSpace: O(1)

Edge cases

  • k equal to len: one window, loop body never runs.
  • k > len must raise or return a sentinel — decide up front.
  • Negative values are fine for FIXED windows (state is exact, not monotonic).

Common mistakes

  • Re-slicing sum(nums[i:i+k]) per position — the O(n·k) this pattern deletes.
  • Off-by-one on the leaving index (right − k, not right − k + 1... after adding right).

Variable-size window (longest, no repeats)

Expand right each step; while the window is invalid, contract left. Record candidates when valid.

Variable-size window (longest, no repeats)
def longest_unique_substring(s: str) -> int:    """Length of longest substring without repeated characters. O(n)."""    last_seen: dict[str, int] = {}    left = 0    best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1     # jump past the duplicate        last_seen[ch] = right        best = max(best, right - left + 1)    return best
Time: O(n) — left never moves backwardsSpace: O(min(n, alphabet))

Edge cases

  • The `>= left` guard: stale positions BEFORE the window must not trigger jumps.
  • Empty string → 0.
  • left jumps (rather than steps) here because the dict stores exact positions — both forms are O(n).

Common mistakes

  • left = last_seen[ch] + 1 without the >= left check, dragging left BACKWARDS on stale entries.
  • Recording best before restoring validity.

Complexity analysis

OperationBestAverageWorstSpace
Fixed window scanO(n)O(n)O(n)O(1)
Variable window (hash state)O(n)O(n)O(n)O(k) state
Recompute-per-window baselineO(n·k)O(n·k)O(n²)O(1)
Window max/min (needs monotonic deque)O(n)O(n)O(n)O(k)

Both pointers move at most n steps forward each — 2n pointer moves total is the entire time proof.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Minimum window substring (the hard-mode template)
from collections import Counterdef min_window(s: str, t: str) -> str:    """Smallest substring of s containing every char of t (with counts).    O(|s| + |t|) time, O(alphabet) space."""    if not t or not s:        return ""    need = Counter(t)    missing = len(t)                     # chars still required (with multiplicity)    best = (float("inf"), 0, 0)          # (length, left, right)    left = 0    for right, ch in enumerate(s, 1):    # right is EXCLUSIVE here        if need[ch] > 0:            missing -= 1        need[ch] -= 1                    # surplus chars go negative

What interviewers expect you to know

Recognition signals

  • 'Longest/shortest/count' + 'substring/subarray/contiguous' + a window-checkable constraint → sliding window.
  • Size given explicitly ('of size k') → fixed; 'longest such that' → variable expand-contract; 'smallest containing' → contract-while-valid.

Validity know-how

  • State must update in O(1) per element in AND out — sums, counts, distinct-trackers qualify; medians and maxes need extra machinery.
  • Positive-only matters for 'sum ≥ target' shrink logic: negatives destroy the monotonicity that justifies contracting (use prefix sums instead).
  • Subsequence problems are NOT windows — contiguity is the entry ticket.

Follow-ups to expect

  • "Why is this O(n) when there's a loop in a loop?" — amortised: left only advances, ≤ n total inner steps.
  • "Window MAXIMUM?" — monotonic deque (next topic) keeps it O(n).
  • "At most K distinct → exactly K?" — atMost(K) − atMost(K−1), a two-call reduction worth memorising.

Common mistakes

Nested-loop window recompute

Recounting the window's contents per position resurrects the O(n²) you were hired to avoid. State updates by the ONE entering and ONE leaving element.

left moving backwards

Stale hash entries (positions before left) must be ignored — the `>= left` guard. A window whose left retreats voids the O(n) proof AND the answers.

Window on negative-number sum constraints

'Shrink while sum ≥ target' assumes shrinking lowers the sum — false with negatives. Reach for prefix sums + hash map instead.

Answer recorded at the wrong time

Maximums record AFTER restoring validity; minimums record INSIDE the valid-shrink loop. Swapping these produces near-miss wrong answers.

Windowing a subsequence problem

'Longest increasing subsequence' has no contiguity — no window applies. Check the word before the technique.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (1)

Medium (7)

Hard (4)

Topic quiz

4 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Complexity1. The variable window has a while-loop inside a for-loop. Why is it still O(n)?
  2. Code output2. longest_unique_substring("abba") returns…
  3. Scenario3. 'Shortest subarray with sum ≥ target' where numbers may be NEGATIVE. Why does the standard shrink fail?
  4. Concept4. 'Exactly K distinct characters' is cleanly solved as…
0 of 4 answered

Frequently asked questions

How is sliding window different from two pointers?

It's the specialisation where both indexes move the same direction and the range BETWEEN them carries maintained state. Converging two-pointers meets in the middle with no window state; the window's essence is incremental bookkeeping.

What state can a window maintain in O(1)?

Sums, counts per value, number of distinct values, matched-character tallies. Order statistics (max/min/median) need auxiliary structures: monotonic deque for max/min, two heaps for median.

Summary & cheat sheet

Key takeaways

  • Windows solve contiguous problems by ±1-element state updates.
  • Fixed: slide both edges. Longest: contract while broken. Shortest: contract while valid.
  • O(n) proof = both pointers move only forward.
  • Negatives break sum-shrink logic; subsequences break contiguity — know the exits (prefix sums, DP).
  • exactly(K) = atMost(K) − atMost(K−1).

Formulas & cheat sheet

  • Window length = right − left + 1 (inclusive edges)
  • Total pointer moves ≤ 2n
  • exactly(K) = atMost(K) − atMost(K−1)

Interview checklist

  • I can write fixed and variable windows without reference.
  • I can state where the answer is recorded in max vs min problems.
  • I can implement minimum window substring with the `missing` counter.
  • I can name the two disqualifiers (negatives on sum-shrink, subsequences).