Pattern 03 of 20

Sliding Window

Keep a contiguous window and update it incrementally instead of recomputing.

When to use it

The answer is a contiguous subarray or substring
Words like longest, shortest, at most k, or contains all of
Recomputing every window from scratch would be quadratic

The idea

Grow the window on the right, shrink it on the left whenever it breaks the rule, and keep a small summary of its contents (a sum, a count map). Each element enters and leaves the window once.

Typical cost O(n) time, O(k) space for the window summary.

How it works

A sliding window is a contiguous range [left, right] that you move across the input while keeping a cheap summary of its contents: a sum, a count map, the number of distinct characters. You never rebuild the summary; you add what enters on the right and remove what leaves on the left.

It is linear because both ends only move forward. Each element enters the window once and leaves at most once, so even though there is a loop inside a loop, the total work is about 2n steps.

There are two families. Fixed-size windows slide one step at a time. Variable-size windows grow until a rule breaks, then shrink from the left until it holds again. The variable version only works when the rule is monotonic: if a window is invalid, every larger window containing it is invalid too.

The pattern hides behind 'longest substring', 'smallest subarray with sum at least', 'at most k distinct', or 'contains all characters of'. If the answer must be contiguous and brute force tries every start and end, think window.

How to attack it

1Confirm the answer is a contiguous subarray or substring.
2Decide whether the window is fixed-size or variable-size.
3Choose the summary that tells you, in O(1), whether the window is valid.
4Write the expand step, the shrink loop, and where to record the answer.
5Check that validity is monotonic; if negatives break it, switch to prefix sums.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def longest_valid_window(s, k):
    # Variable window: longest substring with at most k distinct characters.
    counts = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1         # expand: add s[right]
        while len(counts) > k:                     # shrink while invalid
            out = s[left]
            counts[out] -= 1
            if counts[out] == 0:
                del counts[out]
            left += 1
        best = max(best, right - left + 1)         # window is valid here
    return best


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

Variants

Fixed size k: Add the new element and drop the one k positions back. Averages, maximum sums and anagram detection with a fixed-length pattern.
Longest valid window: Expand every step, shrink only while invalid, record after shrinking. The answer is the widest valid window seen.
Shortest valid window: Expand until valid, then shrink while still valid and record inside the shrink loop. Minimum window covering all required characters.
Exactly k via at most k: Count windows with exactly k distinct items as atMost(k) minus atMost(k - 1).
Window with a deque: Keep a monotonic deque of indices to read the window maximum or minimum in O(1) as it slides.

Pitfalls

Recording the answer before the window has been made valid again.
Using a variable window on arrays with negative numbers, where shrinking does not reduce the sum reliably.
Forgetting to delete zero-count keys, so the distinct count stays too high.
Off-by-one in the window length: it is right - left + 1.
Using if instead of while for the shrink step when one removal may not restore validity.

What it costs

Operation	Cost
Fixed or variable window scan	O(n) time
Window summary as a count map	O(k) or O(alphabet) space
Monotonic deque for window max	O(n) total, O(k) space
Brute force over all windows	O(n²) windows, often O(n³) if each is rescanned

30 Sliding Window problems

Easiest first. Problems marked Free can be solved without Pro.

Solve them in the browser, in Python or JavaScript.

Start free See pricing