Sliding Window Pattern

The sliding window pattern turns an O(n²) brute force over subarrays or substrings into O(n) by maintaining a moving range and updating it incrementally instead of recomputing from scratch. It's one of the most-asked patterns — especially at Meta and ByteDance — so recognizing it instantly is worth a lot.

When to recognize this pattern

• The problem asks about a contiguous subarray or substring (longest, shortest, max sum, contains).
• There's a constraint on the window: a size k, "at most K distinct," "no repeats," or a target sum.
• A brute force would re-scan overlapping ranges — the tell that you can slide instead.

The template

Most variable-size windows follow this shape: expand the right edge, and shrink the left edge while the window violates the constraint.

def sliding_window(s):
    left = 0
    window = {}              # state for the current window
    best = 0
    for right in range(len(s)):
        # 1. include s[right] in the window
        window[s[right]] = window.get(s[right], 0) + 1
        # 2. shrink from the left while the window is invalid
        while invalid(window):
            window[s[left]] -= 1
            left += 1
        # 3. record the answer for this valid window
        best = max(best, right - left + 1)
    return best

Worked examples

Longest substring without repeating characters

Problem: Find the length of the longest substring with all unique characters.

The window is invalid when a character repeats. Track each character's last index and jump left past it.

def lengthOfLongestSubstring(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

O(n) time, O(min(n, charset)) space. The guard last[ch] >= left ensures you only move left for repeats inside the current window.

Maximum sum subarray of size k (fixed window)

Problem: Given an array and integer k, find the maximum sum of any contiguous subarray of size k.

Fixed-size window: add the new element, subtract the one that fell out, track the max.

def max_sum_k(nums, k):
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best

O(n) time, O(1) space. No need to recompute the sum each step — that's the whole point of sliding.

Minimum window substring (hard)

Problem: Given strings s and t, return the smallest substring of s containing all characters of t.

Expand to make the window valid (contains all of t), then shrink to minimize while it stays valid.

from collections import Counter
def minWindow(s, t):
    need = Counter(t)
    missing = len(t)
    left = start = 0
    end = 0
    for right, ch in enumerate(s, 1):
        if need[ch] > 0: missing -= 1
        need[ch] -= 1
        if missing == 0:
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
    return s[start:end]

O(|s| + |t|) time. missing counts how many required characters are still unmatched; the inner while shrinks the window once it's valid.

Variations & pitfalls

• Fixed vs variable window. Fixed-size (size k) just adds/removes one element per step; variable-size shrinks with a while loop until valid.
• "At most K" trick. "Exactly K distinct" = atMost(K) − atMost(K−1) — solve two easier at-most windows.
• Pitfall: forgetting to update the answer only when the window is valid, or shrinking past the valid point. Record the result at the right moment.

FAQ

When should I use the sliding window pattern?

When the problem involves a contiguous subarray or substring with a constraint - longest/shortest/max-sum with a size k, 'at most K distinct,' 'no repeats,' or a target sum. If a brute force would re-scan overlapping ranges, you can usually slide instead for O(n).

What's the difference between a fixed and variable sliding window?

A fixed window of size k adds the new element and removes the one that fell out each step. A variable window expands the right edge and shrinks the left edge with a while loop until the window satisfies (or stops satisfying) the constraint.

What's the time complexity of sliding window solutions?

Almost always O(n): each element enters the window once and leaves at most once, so the two pointers each traverse the array a single time. Space is O(1) or O(k) for the window state.

How do I handle 'exactly K' problems?

Use the at-most trick: exactly K equals atMost(K) minus atMost(K-1). Each at-most sub-problem is a standard sliding window, which is far easier than counting 'exactly' directly.

What's the most common sliding window mistake?

Updating the answer at the wrong time - either before the window is valid, or after over-shrinking. Always record the result at the precise point the window meets the constraint.