Sliding Window

What a sliding window is

Many problems ask about contiguous stretches of an array or string: the best block of k days in a row, the longest run with no repeated letter, the shortest span that adds up to at least some amount. A contiguous stretch is a subarray (for a list) or substring (for a string), and we describe one with two index markers: left, the first position it covers, and right, the last. The pair [left, right] is the window.

The naive way to answer these questions looks at every window separately: for each left, walk every right and scan the items in between. That is two or three nested loops, costing O(n^2) or O(n^3) time — slow as soon as n is large. (We measure cost with Big-O notation, which describes how the work grows with the input size n.)

The sliding-window technique removes the waste. Instead of rebuilding the answer for each window from scratch, it keeps a running summary of the current window — a sum, a set of characters, a table of counts — and updates it cheaply as the window moves. When right steps forward to include a new element, or left steps forward to drop one, we adjust the summary in O(1) rather than rescanning. The window slides across the input once, so the whole job becomes O(n). The art is choosing a summary that updates in constant time and still tells you what you need to know.

Fixed-size windows

The simplest case is a window whose width never changes. Suppose we want the largest sum of any k consecutive elements. Summing each of the n - k + 1 windows from scratch is O(n·k), but two neighbouring windows overlap almost completely: sliding one step right drops the leftmost element and gains one new element on the right. So we sum the first window once, then for each step add the entering element and subtract the leaving one.

def max_sum_k(nums: list[int], k: int) -> int:
    window = sum(nums[:k])       # sum of the first k elements
    best = window
    for right in range(k, len(nums)):   # right is the incoming index
        window += nums[right]           # add the element entering on the right
        window -= nums[right - k]       # subtract the element leaving on the left
        best = max(best, window)
    return best

print(max_sum_k([2, 1, 5, 1, 3, 2], 3))   # -> 9
print(max_sum_k([2, 3, 4, 1, 5], 2))       # -> 7

The element leaving is always k positions behind the one entering, which is why right - k is the index we subtract. Each step does one addition and one subtraction regardless of k, so the loop is O(n) time and O(1) space.

Variable-size windows: expand and shrink

The more powerful pattern lets the window grow and shrink so its width adapts to the data. Both markers still only move forward, but at different rates, in the same two-part loop:

• Expand: move right forward by one to pull a new element into the window, and update the summary to include it.
• Shrink: while the window breaks the rule you care about, move left forward, updating the summary to drop each element that leaves, until the window is valid again.

The key to trusting this pattern is the invariant — the property that holds each time you finish processing a right. For “longest window with no repeated character,” the invariant is the window [left, right] contains no duplicates; you restore it after each expansion by shrinking, and because you measure the answer only when it holds, every measurement is legal.

flowchart LR
    A["expand: right++<br/>add nums[right]"] --> B{"window<br/>valid?"}
    B -->|no| C["shrink: drop nums[left]<br/>left++"]
    C --> B
    B -->|yes| D["record answer"]
    D --> A

Here is the pattern applied to the longest substring with all distinct characters. The summary is a set of the characters currently inside the window, which answers “is this character already here?” in O(1).

def longest_unique(s: str) -> int:
    seen = set()            # characters currently inside the window
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:        # including s[right] would repeat a char
            seen.remove(s[left])       # shrink from the left
            left += 1
        seen.add(s[right])             # now safe to include the new char
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))   # -> 3
print(longest_unique("bbbbb"))      # -> 1
print(longest_unique("pwwkew"))     # -> 3
print(longest_unique(""))           # -> 0

The window width is right - left + 1, and we take the best width seen while the invariant holds. Although there is a while loop inside the for loop, this is still O(n): left only ever moves forward and advances at most n times in total, so the two markers together take at most 2n steps. A common refinement swaps the set for a last-seen dictionary (character to its most recent index) so left can jump straight past a repeat instead of shrinking one step at a time, but the set version is the clearest way to see the pattern.

The window’s state as a hash map

For the distinct-characters problem a set was enough, because each character is either in or out. When the rule is about how many of each item the window holds, the summary becomes a hash map of counts (Python’s collections.Counter is a dictionary specialised for this), and the window is “valid” when its count table matches some target table.

As an example, does a text contain any window that is a rearrangement (a permutation) of a pattern? This is a fixed-size window of width len(pattern), valid exactly when its character counts equal the pattern’s.

from collections import Counter

def has_permutation(text: str, pattern: str) -> bool:
    m = len(pattern)
    if m > len(text):
        return False
    need = Counter(pattern)          # the counts we must match exactly
    window = Counter(text[:m])       # counts inside the first window
    if window == need:
        return True
    for right in range(m, len(text)):
        window[text[right]] += 1             # add the incoming char
        left_char = text[right - m]
        window[left_char] -= 1               # remove the outgoing char
        if window[left_char] == 0:
            del window[left_char]            # drop zero counts so == is exact
        if window == need:
            return True
    return False

print(has_permutation("eidbaooo", "ab"))   # -> True
print(has_permutation("eidboaoo", "ab"))   # -> False

Deleting a count when it reaches zero keeps the table clean, so a plain == between the two Counters is an exact validity test, and each slide stays O(1) in the alphabet size. The lesson is general: whatever “valid” means for your problem, hold just enough state to check it in constant time as elements enter and leave.

A step-by-step trace

Let us trace the variable-size window that finds the smallest subarray whose sum is at least a target, on positive numbers. The summary is a running sum. We expand right to add elements, and while the sum is already large enough we shrink from the left to look for a tighter window.

def min_window_sum(nums: list[int], target: int) -> int:
    left = 0
    window = 0
    best = len(nums) + 1            # sentinel: longer than any real window
    for right in range(len(nums)):
        window += nums[right]           # expand to the right
        while window >= target:         # window is valid; try to shrink it
            best = min(best, right - left + 1)
            window -= nums[left]        # drop the leftmost element
            left += 1
    return best if best <= len(nums) else 0

print(min_window_sum([2, 3, 1, 2, 4, 3], 7))   # -> 2
print(min_window_sum([1, 1, 1, 1], 7))         # -> 0
print(min_window_sum([1, 4, 4], 8))            # -> 2

Walking nums = [2, 3, 1, 2, 4, 3] with target = 7 (indexes written above), each row is one right iteration: the element added, the window sum right after the expand, every shrink the while performs, and the running best width.

index:   0   1   2   3   4   5
value:   2   3   1   2   4   3

The tightest valid window is [4, 3] at indexes 4–5, width 2. Notice left climbed from 0 to 5 across the run, never moving backward — which is why the total shrink work stays bounded by n.

Why it needs a one-way relationship

Sliding window works only when adding or removing an element pushes the constraint in a single, predictable direction. In min_window_sum the numbers are positive, so extending the window can only raise the sum and shrinking can only lower it. That monotonic relationship is what makes the greedy shrink safe: once the sum drops below the target, no smaller window ending at the same right could still reach it, so you can stop shrinking.

Introduce negative numbers and that guarantee collapses. Adding an element can now lower the sum and dropping one can raise it, so a window that fell short might become valid later, or a smaller valid window might hide past a dip. The same function then gives a wrong answer:

# min_window_sum assumes positive numbers.
print(min_window_sum([3, -2, 5], 4))   # -> 3  (WRONG: the single element 5 is a window of length 1)

The true smallest window is just [5], width 1, but the sum-based shrink never considers it because the running sum does not move in one direction. When the monotonic relationship is gone, sliding window is the wrong tool (reach for a prefix-sum table with a hash map instead). Before applying the pattern, always check: does one element entering the window move the constraint only one way?

Common pitfalls

• Shrinking with an if instead of a while. After an expansion the window may violate the rule by more than one element, so you often need to shrink repeatedly. A single if fixes only one step and leaves the invariant broken.
• Measuring while the window is invalid. Record the answer only at a point where the invariant holds — after the shrink loop for a “longest valid” problem, and inside the shrink loop for a “shortest valid” one. Reading the width at the wrong moment counts an illegal window.
• Off-by-one on width. The window [left, right] holds right - left + 1 elements, not right - left. Forgetting the + 1 undercounts by one every time.
• Letting left move backward. Both markers must only advance. If you use a last-seen dictionary to jump left, guard it so a stale index from a character that already left the window cannot drag left back and inflate the window.
• Applying it to non-monotonic data. As shown above, the sum-window pattern is silently wrong on negative numbers. Confirm the one-way relationship first.

Big-O summary

Practice

1. Write a fixed-window function max_average_k(nums, k) that returns the largest average of any k consecutive elements. Reuse the add-and-subtract idea from max_sum_k and divide by k only at the end. Test it on [1, 12, -5, -6, 50, 3] with k = 4 and confirm you get 12.75.

2. Adapt longest_unique into longest_at_most_two(s): the longest substring containing at most two distinct characters. Use a Counter as the window state and shrink from the left whenever the number of distinct keys exceeds two. Check that "eceba" gives 3 (the substring "ece").

3. Explain in one or two sentences why min_window_sum cannot be trusted on a list that contains negative numbers, then construct your own small example where it returns a length larger than the true smallest window.