🧩 Data Structures & Algorithms · Chapter 5

Sliding window

To move a 7-day window forward one day, you don't re-add all seven days. You add the new day and subtract the one that fell off. That one idea turns O(n·k) into O(n).

Study this lesson free in the app →

The basics

A sliding window is a contiguous stretch of an array or string — from index left to right — that moves forward through the data, updating a running answer as items enter on the right and leave on the left.

The problem it solves: questions about contiguous runs — the best 7-day sales total, the longest stretch of text with no repeated letter, the shortest run of numbers reaching a target. Checking every possible run separately is O(n²) or worse. A window reuses work: when it slides one step, only one item enters and one leaves, so each update is O(1) and the whole scan is O(n) time, usually with O(1) extra space (or O(k) for a set or map of what's inside).

The mental model: a train window. As the train moves, one tree appears at the front edge of the view and one disappears at the back. You don't re-look at everything in between.

Explained

"Which 7 consecutive days had the highest step count this year?"

Brute force: for each of the 359 possible weeks, add up 7 days. About 2,500 additions — fine for a year, painful for a decade of minute-by-minute data.

Sliding window: add up the first week once. Then for every later week, add the new day, subtract the day that fell off. Two operations per step, whatever the window size.

The weekly rainfall board

A village notice board shows "rain in the last 7 days" and is updated every morning.

The new caretaker, on day one, reads the last seven entries from the logbook and adds them up: 3 + 0 + 12 + 5 + 0 + 0 + 8 = 28 mm.

The next morning they don't redo the whole sum. Yesterday brought 4 mm, and the day that just dropped out of the week had 3 mm. 28 + 4 − 3 = 29 mm. Done in five seconds.

A month later the council asks for a 30-day figure. The caretaker shrugs — the update is still add one, subtract one. That's why the window technique doesn't care how big k is.

Two kinds of window

Fixed size k — e.g. maximum sum of any k consecutive numbers.

1. window = sum(a[0:k]), best = window.
2. For i from k to n − 1: window += a[i] - a[i - k]; best = max(best, window).

O(n) time, O(1) space.

Variable size — the window grows and shrinks to satisfy a rule.

• Longest valid (longest substring with no repeated character): extend right; while the window breaks the rule, move left forward. Record the length after fixing.
• Shortest valid (shortest run with sum ≥ target, positive numbers): extend right; while the window satisfies the rule, record its length, then move left forward to try a shorter one.

Why the nested loop is still O(n): left and right each only move forward and each travels at most n positions. Total pointer moves ≤ 2n.

Fixed window, k = 3

First window [2, 1, 5] = 8. Slide: +1 −2 → 7. Slide: +3 −1 → 9 for [5, 1, 3]. Slide: +2 −5 → 6. Four windows, each updated with one addition and one subtraction. Maximum: 9.

Watch a big value enter and leave

The 9 enters on the second slide and the sum jumps from 6 to 14 — the maximum, for [3, 2, 9]. It stays inside for three windows (14, 12, 12), then leaves and the sum crashes to 4. The window never re-adds anything: the 9 is added exactly once and subtracted exactly once.

Fixed and variable, side by side

def max_sum_k(a, k):                     # fixed window
    window = sum(a[:k])
    best = window
    for i in range(k, len(a)):
        window += a[i] - a[i - k]        # one in, one out
        best = max(best, window)
    return best                          # O(n) time, O(1) space

def longest_unique(s):                   # variable window
    last = {}                            # char -> last index seen
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1          # jump past the repeat
        last[ch] = right
        best = max(best, right - left + 1)
    return best                          # O(n) time, O(alphabet) space

max_sum_k([2, 1, 5, 1, 3, 2], 3)         # 9
longest_unique("abcabcbb")               # 3  ("abc")
longest_unique("pwwkew")                 # 3  ("wke")

The last[ch] >= left check matters: a repeat that's already outside the window must not drag left backwards.

Complexity, and where windows run for real

| Approach | Time | Space | | --- | --- | --- | | Every subarray, summed from scratch | O(n³) | O(1) | | Every subarray, running sum | O(n²) | O(1) | | Fixed window of size k, recomputed | O(n·k) | O(1) | | Sliding window | O(n) | O(1) – O(k) |

With n = 10⁶ and k = 1,000, recomputing is a billion additions; sliding is two million.

The same idea runs production systems: rate limiters ("at most 100 requests in any 60 seconds"), moving averages on dashboards, streaming aggregations in tools like Kafka Streams and Flink ("sales per 5-minute window"), and network protocols that cap how much unacknowledged data is in flight. In every case the window state is updated incrementally because the stream never ends — recomputing isn't an option.

Gotchas

• Negative numbers with sum-based shrinking — dropping an item can raise the sum, so "shrink while ≥ target" misses answers. Use prefix sums with a hash map.
• Off-by-one on length — the window [left, right] holds right - left + 1 items.
• Letting left move backwards — in longest-unique, a stale repeat outside the window must be ignored: left = max(left, last[ch] + 1).
• Recording the answer in the wrong place — longest: after fixing the window; shortest: inside the shrink loop, before removing.
• Using it on non-contiguous problems — subsequences (gaps allowed) need other tools, often dynamic programming.
• k larger than the array — handle it before computing the first window.

Words to know

In two minutes

• A window is a contiguous range [left, right] that slides forward; each move adds one item and removes one, so it updates in O(1).
• Fixed size k: compute the first window's sum, then window += a[i] - a[i - k]. O(n) time, O(1) space — versus O(n·k) recomputing each window.
• Variable size: always extend right; move left forward while the window is invalid (longest-valid problems) or while it is still valid (shortest-valid problems).
• Each index enters the window once and leaves at most once, so even with a nested while, the total work is O(n).
• Track the window with a running sum, a counter, or a hash map of last-seen positions — O(1) or O(alphabet) extra space.
• Sum-based shrinking needs non-negative numbers: with negatives, removing an item can make the sum bigger, and the logic breaks (use prefix sums instead).
• Recognise it by the words: contiguous, subarray, substring, 'longest', 'shortest', 'at most k', 'in the last k'.

Test yourself

There are 9 questions, 4 puzzles and 5 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.