leetExpert

Module 11 · Sliding Window

Practice

Practice~1 min

How to practice this module

Sliding-window drills are invariant maintenance: decide what the window guarantees, then expand and shrink to keep it. Start with the fixed-size average, then the dynamic shrink invariant; permutation and minimum-window both use a "covered characters" counter. Done when all five show Solved in the hub.

Problems

Sliding Window — work them in order; difficulty ascends.

0/5

solved

  1. 1Maximum Average Subarray IEasyFixed-size windowWatch for: Slide one element at a time and recompute incrementally, never per window
  2. 2Minimum Size Subarray SumMediumDynamic shrinkWatch for: Shrink the left end while the sum still meets the target; update the answer on every valid window
  3. 3Longest Substring Without Repeating CharactersMediumWindow + last-seen mapWatch for: The left bound jumps to just after the previous occurrence — do not increment it by one
  4. 4Permutation in StringMediumCount-match windowWatch for: Match means all 26 letter counts are equal, not merely that the window length fits
  5. 5Minimum Window SubstringHardCoverage counterWatch for: Expand until every character is covered, then shrink until coverage breaks; record the answer while coverage holds

Cheatsheet

Sliding Window — Grow the right edge, shrink the left — maintain a window invariant.

Smell → pattern

  • Longest / shortest subarray with a propertyVariable window
  • Fixed length k aggregateFixed window
  • At most K distinct / replacementsCount map + shrink
  • Anagram / permutation in a stringNeed map + deficit

Patterns

Variable window

Core

Smell: Max length while invariant holds

Expand R freely; while the invariant breaks, advance L. Answer updates when the window is valid.

LRwindow

Fixed window of k

Safe

Smell: Best score on every block of k

Maintain a running sum (or structure) for indices [i−k+1, i]. Slide by adding the entering element and dropping the leaving one.

LRwindow

Distinct / frequency budget

Reach

Smell: At most K different characters

Map counts inside the window. When distinct > K (or a budget breaks), shrink from L until legal again.

0123

Need / have matching

Careful

Smell: Window must cover required counts

Track how many constraints are satisfied. Expand until ‘need’ is met, then shrink to minimise — classic minimum-window shape.

LRwindow

Complexity targets

  • Variable window scan

    Time
    O(n)
    Space
    O(Σ)
    Note
    Each index enters/leaves once

  • Fixed window

    Time
    O(n)
    Space
    O(1)
    Note
    Often just a running sum

  • Covering window

    Time
    O(n)
    Space
    O(Σ)
    Note
    Two maps or one + deficit

Traps

  • Updating the answer at the wrong time

    Max-length updates when valid; min-length updates after you’ve satisfied the need and while shrinking. Mixing them is a silent wrong answer.

  • Forgetting to erase zero counts

    If you use map.size / distinct counters, delete keys (or decrement a distinct tally) when a count hits zero — stale keys inflate distinct.