Sliding Window 101

What a sliding window is

The idea

A sliding window is a contiguous range [left, right] of an array or string that you move from left to right while keeping a small summary of what is inside: a running sum, a count of zeros, or a frequency map of characters. Instead of recomputing that summary for every one of the O(n²) subarrays, you update it in O(1) when an element enters on the right or leaves on the left. Each element enters once and leaves once, so the whole scan is O(n).

Two kinds of window

1. Fixed size. The window always has length k. Add the new element, remove the one that fell off, record the answer.
2. Variable size. The window grows on the right until it breaks (or meets) a condition, then shrinks from the left until it is valid again. The answer is the best window seen.

Signals in a problem statement

• "Contiguous subarray" or "substring" (not subsequence).
• "Longest", "shortest", "maximum", "minimum" length or sum.
• "At most k" changes, distinct characters, zeros you may flip.
• "Average of every window of size k".
• "Smallest substring containing all characters of another string".

When it does not work

The variable window relies on monotonic validity: if a window is valid, shrinking it keeps it valid (or growing it keeps it invalid), so the left pointer never needs to move backwards. With negative numbers in a "sum at least k" question this breaks, because adding an element can lower the sum. In that case reach for prefix sums with a hash map or a monotonic deque instead. Asking "are all numbers non-negative?" is a smart clarifying question that interviewers notice.

Core patterns with templates

1. Fixed-size window

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

2. Longest valid window (grow, then shrink while invalid)

Longest run of ones if you may flip at most k zeros:

def longest_ones(nums, k):
    left = zeros = best = 0
    for right, x in enumerate(nums):
        zeros += x == 0
        while zeros > k:
            zeros -= nums[left] == 0
            left += 1
        best = max(best, right - left + 1)
    return best

3. Shortest valid window (grow until valid, then shrink while still valid)

Smallest length with sum at least target (all numbers positive):

def min_subarray_len(target, nums):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

Example: target = 7, nums = [2,3,1,2,4,3]. The window [4,3] at the end has length 2, the answer.

4. Window with a frequency map

For "smallest substring of s containing every character of t", keep need = Counter(t) and a count missing = len(t). When s[right] is still needed, decrement missing. When missing == 0, record the window and shrink from the left, giving characters back to need and incrementing missing when a needed character leaves.

The difference between pattern 2 and pattern 3 is where you record the answer: after the shrink loop for "longest", inside it for "shortest".

Complexity, mistakes and edge cases

Complexity

Every element is added once and removed at most once, so both window types run in O(n) time, even with a while inside the for. Space is O(1) for sums and counts, or O(alphabet) for a frequency map.

Common mistakes

• Recording the answer in the wrong place. Longest-window answers go after shrinking; shortest-window answers go inside the shrink loop.
• Window length off by one. With inclusive left and right the length is right - left + 1.
• Using a window on data with negatives when validity is not monotonic. Check the constraints first.
• Forgetting the "no answer" case. Return 0 or an empty string when no window ever became valid, instead of inf.
• Shrinking with if instead of while. Usually one step is not enough to restore validity. (There is a well-known trick for longest-window problems where an if works because the window never shrinks below the best size, but use it only if you can explain it.)
• Comparing whole maps every step. Checking window_counts == need costs O(alphabet) per step; maintain a single missing or formed counter instead.

Edge cases

k larger than the array, k = 0, empty string t, t longer than s, all elements satisfying the condition, none satisfying it, repeated characters in t (you need each copy), and uppercase versus lowercase letters.

Checking your loop by hand

Dry-run with a five-element example and write the window after each step as [left..right] summary. If left ever exceeds right + 1, or the summary disagrees with the actual window contents, you have found your bug before the interviewer does.

Variations and practise

How interviewers twist it

• "At most k distinct characters". Keep a counter of characters in the window; shrink while len(counter) > k, deleting keys whose count drops to zero.
• "Exactly k". Compute at_most(k) - at_most(k - 1). This converts an awkward condition into two easy windows.
• Permutation or anagram inside a string. A fixed window of size len(p) with a count comparison.
• Maximum in every window. A monotonic deque keeps candidates in decreasing order; the front is the maximum. This is the bridge to the Stack & Queue card.
• Longest substring without repeating characters. Store the last index of each character and jump left directly past the previous occurrence.
• Streaming data. If elements arrive one at a time, a fixed window is just a queue of the last k items plus a running summary.

Talking about it in the interview

State the invariant: "the window always contains at most k zeros" or "missing is the number of characters of t still not covered". Then the code is just maintaining that invariant on every add and remove.

Practise

The problems below include a fixed-size average, two variable windows (one longest, one shortest), and the classic frequency-map window that appears in many product-company interviews. For each, decide first whether you are looking for the longest or the shortest window, because that decides where the answer is recorded.