Lesson

Sliding Window

The intuition: a window on a train

Picture yourself on a train, looking out the window. The scenery keeps sliding by: something leaves your view on the left, something new appears on the right. To know what you can see right now, you don't have to re-examine the whole track. You only need to account for what came in and what went out.

That's the whole idea behind the sliding window. A window is a contiguous piece of an array or string from index left to right. We slide it across the data and update the answer in O(1) per step, instead of recomputing the whole piece from scratch.

You can spot a window problem by words like "subarray", "substring", "consecutive" and "longest / shortest / maximum sum".

Fixed-size window

Say you need the sum of every k consecutive elements. Brute force would add up k numbers for every starting point, which is O(n·k).

A window makes it simple. Compute the sum of the first k elements, then on each step:

add the element entering on the right, a[right];
subtract the element leaving on the left, a[right - k].

In short, sum += a[right] - a[right - k]. One pass, O(n). The window size never changes; it just slides right like a frame.

Variable-size window

It gets more interesting when you don't know the window length up front and have to find it. Let's take our own example: find the length of the longest subarray with sum ≤ limit (all numbers are non-negative).

Think of a caterpillar:

The head (right) always crawls forward and grabs a new element.
If the window turns "bad" (sum > limit), the tail (left) catches up until the window is good again.
Now the window is valid, and you can update the answer.

Take [2, 1, 3, 2, 4, 1] and limit = 6.

Moment 1. right has reached index 2. The sum is 2+1+3 = 6, which is ≤ 6, so the window is good, length 3.

left ↓ 20

right ↓ 32

Window [0..2]: sum 6 ≤ 6, length 3 — best answer so far

Moment 2. right steps to index 3, and the sum becomes 8 > 6. The window is broken, so we shrink it: drop a[0] = 2, the sum is 6, left = 1. The window is good again.

left ↓ 11

right ↓ 23

Added 2 → sum 8, moved left → sum 6, window [1..3] is valid again

Notice that left never moves back. Both pointers only ever move right.

The variable-window template

def longest_with_sum_at_most(a, limit):
    left = 0
    window_sum = 0
    best = 0
    for right in range(len(a)):
        window_sum += a[right]          # expand: take a[right]
        while window_sum > limit:       # while the condition is broken
            window_sum -= a[left]       # drop the element on the left
            left += 1
        best = max(best, right - left + 1)  # window is valid — update the answer
    return best

This skeleton fits almost any variable-window problem. Only three things change: what you track about the window's state, when the window is bad, and what you update in the answer.

The same thing on a string

On a string the scheme is identical; only the window's state changes. Usually it's a character-count map. Say the condition is "at most two distinct letters in the window". Then:

when you move right, do count[s[right]] += 1;
the window is bad if len(count) > 2;
when you move left, decrement count[s[left]], and if it hits zero, delete the key.

First put into words what "the window is bad" means. Once you can say that, the code practically writes itself.

Why it's O(n) despite the nested loop

The nested while often scares people: it looks like O(n²). But let's count pointer moves:

right walks the array once, that's n steps;
left also only moves forward and makes at most n steps in total.

Every element enters the window once (via right) and leaves at most once (via left). That's at most 2n operations, so O(n) time. Memory is O(1) for a sum or O(alphabet size) for a counter.

Approach	Time	Memory
Brute force over all subarrays	O(n²) or O(n³)	O(1)
Sliding window	O(n)	O(1) / O(σ)

How it sounds in an interview

"Brute force over all subarrays is O(n²). Notice that once the window goes bad, there's no point expanding it further; we need to shrink it from the left. So I'll use two pointers: right expands the window, left shrinks it while the condition is broken. Each element enters and leaves the window at most once, so it's O(n) overall."

A strong signal for the interviewer is when you explain on your own why the window is monotonic: expanding can only make the condition worse, and shrinking can only make it better.

Common mistakes

Negative numbers. If there are any, "sum > limit → shrink" stops working: shrinking can make the sum bigger. A window works when the condition is monotonic. Otherwise prefix sums usually help; they're the next lesson.
if instead of while. One step of left may not be enough; keep shrinking until the window is valid.
Updating the answer in the wrong place. For "longest", update after the while, once the window is good. For "shortest", you usually update inside the while, while the window still satisfies the condition.
Window length. It's right - left + 1, and that +1 is easy to forget.
Junk in the counter. If you don't delete keys that hit zero, len(count) will lie to you.

If you've got the caterpillar down — "head goes forward, tail catches up while things are bad" — you already know the core of it. In the practice that follows, you'll apply this same skeleton to different conditions.