Sliding window

The sliding window coding pattern for interviews, fixed and variable size. How to spot it, the grow-and-shrink template, a step-through of longest substring without repeats, code in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Mid-level14 min read

Read first: Two pointers

“Find the longest substring with no repeated letter.” For a text of n letters, the brute force tries every start and every end. That’s O(n²) windows, and it checks each one, which can make it O(n³). But neighboring windows share almost everything. The window from 2 to 7 and the window from 2 to 8 differ by one letter. So rechecking all of it is wasted work.

A sliding window keeps one window, [left, right], and the facts about it (a set of letters, a sum, a count per letter). Moving right adds one element, moving left removes one, and each update is O(1). Both edges only move forward, so the whole scan is O(n). It’s two pointers where the pointers bound a range instead of marking a pair.

How to spot it

“Contiguous” or “substring” or “subarray” together with “longest”, “shortest”, “maximum” or “minimum”.
A rule about what’s inside the window: at most k distinct letters, no repeats, sum at least target, contains every letter of another string.
A fixed length k in the statement: averages, max sum of k consecutive elements, anagrams of a pattern inside a string.

It is not a sliding window when the elements don’t have to be next to each other. That’s usually dynamic programming. It’s also not one when the rule isn’t monotonic, such as “subarray sum exactly k” with negative numbers. That’s prefix sums.

Watch it run

Longest stretch of "abcbadcb" with no repeated letter. The yellow band is the window. When right reaches a letter that’s already inside, the window is broken, and left moves forward until the old copy is gone. Only then is the length measured.

text

a0b1c2b3a4d5c6b7

left

in window

empty

best

seen = set(); left = best = 0
for right, letter in enumerate(text):
while letter in seen: # broken: shrink
seen.remove(text[left]); left += 1
seen.add(letter) # valid again
best = max(best, right - left + 1)

Find the longest stretch of "abcbadcb" with no repeated letter. The window is everything from left to right.

1 / 13

Count the moves. right moves 8 times, and left moves at most 8 times. The while loop inside the for loop looks like O(n²). But left never moves backward, so across the whole run it does at most n steps in total. That’s called an “amortized” argument. It’s what you say when an interviewer asks about the nested loop.

The template

The two shapes of variable window: longest valid (shrink while invalid) and shortest valid (shrink while valid).

SlidingWindow.javaexample.pySlidingWindow.csmain.goexample.ts

import java.util.HashSet;
import java.util.Set;

public class SlidingWindow {
    static int longestUnique(String text) {
        // Longest valid window: grow right every step; when the new character breaks the rule
        // ("no repeats"), shrink from the left until it holds again. Each index enters once and
        // leaves at most once, so this is O(n) even with the inner while.
        Set<Character> seen = new HashSet<>();
        int left = 0, best = 0;
        for (int right = 0; right < text.length(); right++) {
            char letter = text.charAt(right);
            while (seen.contains(letter)) seen.remove(text.charAt(left++));
            seen.add(letter);
            best = Math.max(best, right - left + 1); // measured only while valid
        }
        return best;
    }

    static int minSubarrayLen(int target, int[] nums) {
        // Shortest valid window: grow until the rule holds ("sum >= target"), then shrink
        // while it still holds, recording each valid length. Correct only because every number
        // is positive: adding grows the sum and removing shrinks it.
        int left = 0, total = 0, best = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            total += nums[right];
            while (total >= target) {
                best = Math.min(best, right - left + 1);
                total -= nums[left++];
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    public static void main(String[] args) {
        check(longestUnique("abcbadcb") == 4);
        check(longestUnique("") == 0);
        check(longestUnique("bbbb") == 1);
        check(minSubarrayLen(7, new int[] {2, 3, 1, 2, 4, 3}) == 2);
        check(minSubarrayLen(100, new int[] {1, 2, 3}) == 0);
        System.out.println("ok: longestUnique and minSubarrayLen");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

Write any variable window by answering three questions first:

What state do I keep? A set, a count map, a running sum, the number of letters still missing.
When is the window invalid (for longest) or valid (for shortest)? This must be O(1) to check from the state.
When do I record the answer? For longest, after shrinking, when the window is valid again. For shortest, inside the shrink loop, while it’s still valid.

Fixed-size windows

When the length is fixed at k (window_size in code), there’s no shrink loop. Add nums[right], and once right >= window_size, remove nums[right - window_size]. Permutation in string is this shape: a window the length of the pattern, compared by letter counts, where each slide changes two counts.

Tracking “how many are still missing”

Minimum window substring asks for the shortest window containing every letter of target_text, with duplicates. Comparing two count maps at every step is O(26) or O(distinct letters). Instead keep one number, missing, the count of required letters not yet covered. It drops when a needed letter enters and rises when one leaves, so validity is missing == 0, an O(1) check.

Complexity

Every variable window is O(n) time, because each index enters once and leaves at most once. Memory is the size of the state: O(1) for a sum, O(k) for a set of up to k distinct items, O(alphabet) for letter counts.

Sliding window maximum is the exception that needs more. It asks for the largest value in each window of size k. A max can’t be “removed” in O(1) when it slides out. So the window keeps a monotonic deque of candidates instead. It’s the same idea as the monotonic stack, and it stays O(n).

Say this out loud

The answer is a contiguous range, and a window that breaks the rule only gets worse as it grows, so I’ll slide a window. Both edges only move forward, so it’s O(n) even with the inner while loop.

Interview questions

Interviewer asksYour solution has a while loop inside a for loop. Isn't that O(n²)?

No. Each iteration of the inner loop moves left forward by one, and left never moves back or passes the end. So across the whole run the inner loop runs at most n times in total. The total work is O(n) for right plus O(n) for left.

Interviewer asksLongest substring with at most k distinct characters: what's the state and the rule?

A map from character to count inside the window. The window is invalid when the map has more than k keys. When shrinking, decrement the left character’s count and delete the key when it reaches 0, so the number of keys stays accurate. Record the length after shrinking.

Interviewer asksLongest repeating character replacement: why don't you decrease the max count when shrinking?

The answer only improves when a window has a higher max count than any window before it. A stale, too-high max count can make the window look valid when it isn’t. But it only keeps the window from shrinking. The length it reports was already reached earlier. So the answer is still correct, and you skip an O(26) rescan on every step. This one is subtle. Saying why it’s safe is a strong signal.

Practice

10 problems on LeetCode: 2 easy, 6 medium, 2 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

Use it when the answer is a contiguous subarray or substring, and the question is longest, shortest or a fixed length k.
State: whatever answers “is this window valid?” in O(1).
Longest: grow, shrink while invalid, record. Shortest: grow, record and shrink while valid. Fixed: add one, remove one.
Cost: O(n) time, since both edges only move forward.
Check first: the rule must be monotonic. With negative numbers, use prefix sums instead.