Sliding window

When a problem asks about a run of neighboring items, keep a window over the run and update it as it slides instead of recomputing it: each item enters once and leaves once.

3 examples14 to practiceRead · 5 min
The idea

Don't recompute the run: add what enters and remove what leaves

A subarray is a run of neighboring items in a list, and a substring is the same thing in a string: positions L to R, with nothing skipped. Many problems ask for the best such run: the largest sum of 4 neighbors, the longest stretch without a repeated letter.

Checking every run separately costs at least O(n²). A sliding window keeps one run, positions L to R, together with whatever summary the problem needs (a sum, a count of each letter). Moving the window one step changes the summary by exactly one item entering and maybe one leaving, which is O(1) work.

The rule

A sliding window visits each item twice at most, once when it enters at R and once when it leaves at L, so a whole scan is O(n). It works when the window's summary can be updated one item at a time.

Spotting it

"Contiguous" plus "longest", "shortest" or "of length k"

A subarray or substring of length k

Fixed size: slide one step at a time

The longest run such that a rule holds

Grows at R, shrinks at L while the rule is broken

The shortest run whose sum reaches a target (positive numbers)

Grows until the target is met, then shrinks while it still is

"At most k distinct", "no repeats", "contains every letter of"

A count per item inside the window

Basic

The best average of k neighbors

A fixed window of 4. Summing each window from scratch would be 4 additions per position; sliding it is two: add the new item on the right, subtract the one that falls off the left.

Medium

The longest stretch without a repeated letter

Now the window's size isn't given. It grows by one letter at a time on the right. When the new letter is already in the window, the rule is broken, so the left edge moves right, dropping letters, until the repeat is gone. A count of each letter in the window tells you instantly whether a letter repeats.

The left edge only ever moves right, so across the whole scan it moves at most n times. Growing and shrinking together are O(n), even though the shrinking sits in a loop inside a loop.

Hard

Grow until the window works, shrink while it still does

Now the window's rule is "contains every letter of t". It grows on the right until the rule holds, then shrinks from the left for as long as it still holds, recording each valid window. A count per letter, plus one number for how many letters are still missing, answers "does it hold?" in O(1) instead of rechecking every count.

The template

The shape to reuse

The template: the longest window that keeps a rule
  1. 1L ← 0
  2. 2for R from 0 to length of xs − 1
  3. 3 add xs[R] to the window
  4. 4 while the window breaks the rule
  5. 5 remove xs[L] from the window
  6. 6 L ← L + 1
  7. 7 record the window if it is the best so far
The other shape: the shortest window that meets a goal
  1. 1L ← 0
  2. 2for R from 0 to length of xs − 1
  3. 3 add xs[R] to the window
  4. 4 while the window meets the goal
  5. 5 record the window if it is the shortest so far
  6. 6 remove xs[L] from the window
  7. 7 L ← L + 1

The difference is where the record happens. For the longest window, shrink until the rule holds again, then record. For the shortest, record while the goal still holds, then shrink to try a smaller one. The Hard walkthrough uses the second shape.

For a fixed size k, the inner loop becomes a single step: once the window holds k items, remove xs[R − k] each time you add xs[R].

Traps

Where window solutions go wrong

Negative numbers in sum problems

Shrinking when the sum is too big assumes that removing an item lowers the sum. With negative numbers that is false, and the window logic breaks; Prefix sums handles those problems instead.

`if` instead of `while` when shrinking

One step left may not be enough to repair the window.

Not contiguous

If the problem allows skipping items (a subsequence, not a subarray), a window doesn't apply.

Off-by-one lengths

The window from L to R holds R − L + 1 items.

Check yourself

3 questions

1. A window runs from position L = 3 to R = 7. How many items does it hold?
2. The variable-size template has a while loop inside a for loop. Why is the whole scan still O(n)?
3. You need the shortest run whose sum reaches 10, and the list has negative numbers. Does shrinking from L still work?
Takeaways

Remember this

  • A sliding window keeps one run of neighbors and updates its summary as items enter and leave: O(n) for the whole scan.
  • Fixed-size windows slide one step at a time; variable windows grow at R and shrink at L while a rule is broken.
  • Shrinking on sums needs non-negative numbers; with negatives, use prefix sums instead.
Practice

Now solve some yourself

Only this topic 0 of 9 solved

  1. Easy
    A repeat within k places
    Sliding window
    LeetCode 219(opens in a new tab)
  2. Medium
    Most vowels in a stretch of k letters
    Sliding window
    LeetCode 1456(opens in a new tab)
  3. Medium
    Most books read within a time limit
    Sliding window
    Codeforces 279B(opens in a new tab)
  4. Medium
    Shortest run reaching a target sum
    Sliding window
    LeetCode 209(opens in a new tab)
  5. Medium
    Longest run of ones after flipping k zeros
    Sliding window
    LeetCode 1004(opens in a new tab)
  6. Medium
    Longest run of one letter after k changes
    Sliding window
    LeetCode 424(opens in a new tab)
  7. Medium
    Longest run with at most two kinds
    Sliding window
    LeetCode 904(opens in a new tab)
  8. Medium
    Longest run of ones after deleting one item
    Sliding window
    LeetCode 1493(opens in a new tab)
  9. Medium
    Runs whose product stays under k
    Sliding window
    LeetCode 713(opens in a new tab)

Mixed with topics you have practiced 0 unlocked

    5 more once you have practiced Hash tables & maps, Monotonic stack & queue. Play one of its examples to the end and solve one of its problems to unlock them.

    Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.

    Next

    Prefix sums

    Continue