The Sliding Window Algorithm: Template and Eight Worked Problems

The sliding window algorithm turns a nested loop over every subarray into a single pass with two indices. It is the highest-leverage pattern in interview preparation, because the questions it solves — the longest substring with some property, the shortest subarray reaching some total, every window of length k — are extremely common and the code is nearly identical every time.

This walks through the two forms, one template, eight worked problems in Python with their complexity, and the three cases where a window is the wrong tool.

Fixed windows and variable windows#

Everything in this pattern is one of two shapes.

A fixed window has a length the problem gives you. Both ends move together, one step at a time, and the window's summary is updated by adding the element that entered and subtracting the one that left. There is no inner loop. Use it when the question is about every subarray of length k.

A variable window grows on the right unconditionally, and shrinks from the left only while it violates a constraint. Its length is the answer, or part of it. Use it when the question is about the longest or shortest stretch satisfying a condition.

The thing they share is the running summary — a sum, a count of zeroes, a character frequency map — which must be updatable in O(1) when a single element enters or leaves. That property is the whole reason the pattern is linear, and if you cannot maintain it cheaply, the window will not help you.

The sliding window algorithm template#

Here is the variable form as a complete function. Every variable-window problem below is this with a different legality test.

def longest_subarray_with_sum_at_most(nums, k):
    """Longest contiguous run whose sum is at most k. Assumes nums are non-negative."""
    left = 0
    window = 0
    best = 0

    for right, value in enumerate(nums):
        window += value

        while left <= right and window > k:
            window -= nums[left]
            left += 1

        best = max(best, right - left + 1)

    return best

Four things about this shape are worth internalising:

1. right always moves forward. It never goes back, and it is driven by the for, not by a condition.
2. left only moves inside the while. It moves as many times as it needs to and never more; the left <= right guard stops it running past the window when no legal window exists.
3. The window is legal at the bottom of the loop. That is why best is updated there and nowhere else.
4. The cost is O(n) even though there is a nested loop. left advances at most n times across the entire run, so the total work is at most 2n — each element enters once and leaves at most once.

The non-negativity note in the docstring is the load-bearing assumption. With negative numbers, adding an element can decrease the sum, so "too big" is no longer permanent, and the shrink step throws away windows that would have become legal again.

Eight worked problems#

Ordered by difficulty, and by how much each one adds to the template.

1. Maximum Average Subarray I — the fixed window#

Problem 643. Given k, find the maximum average of any subarray of length exactly k.

def find_max_average(nums, k):
    window = sum(nums[:k])
    best = window

    for right in range(k, len(nums)):
        left = right - k
        window += nums[right] - nums[left]
        best = max(best, window)

    return best / k

Compare the sums, divide once at the end — dividing inside the loop introduces floating point error for no reason. O(n) time, O(1) space.

2. Maximum Number of Vowels in a Substring — a fixed window over a string#

Problem 1456. Same machinery, but the summary is a count rather than a sum.

def max_vowels(s, k):
    vowels = set("aeiou")
    window = sum(1 for char in s[:k] if char in vowels)
    best = window

    for right in range(k, len(s)):
        window += (s[right] in vowels) - (s[right - k] in vowels)
        best = max(best, window)

    return best

Booleans are integers in Python, so the enter-minus-leave update is one line. O(n) time, O(1) space.

3. Longest Substring Without Repeating Characters — the jumping left pointer#

Problem 3. The first variable window, and the one that teaches the most.

def length_of_longest_substring(s):
    last_seen = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        best = max(best, right - left + 1)

    return best

Instead of shrinking one step at a time, left jumps straight past the previous occurrence. The last_seen[char] >= left guard is the bug everyone hits: a repeat that sits before the current window must not drag left backwards. O(n) time, O(min(n, alphabet)) space.

4. Max Consecutive Ones III — a budget instead of a rule#

Problem 1004. You may flip up to k zeroes; find the longest run of ones.

def longest_ones(nums, k):
    left = 0
    zeros = 0
    best = 0

    for right, value in enumerate(nums):
        if value == 0:
            zeros += 1

        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

Recognising "you may violate the rule k times" as "the window may contain at most k bad elements" is most of the work. This is the template with one counter. O(n) time, O(1) space.

5. Longest Repeating Character Replacement — the window that never shrinks#

Problem 424. Replace up to k characters to get the longest run of one letter.

def character_replacement(s, k):
    counts = {}
    left = 0
    most_common = 0
    best = 0

    for right, char in enumerate(s):
        counts[char] = counts.get(char, 0) + 1
        most_common = max(most_common, counts[char])

        if right - left + 1 - most_common > k:
            counts[s[left]] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

The window size minus the most common letter's count is the number of replacements needed. Two things surprise people: the shrink is an if, not a while, and most_common is never decreased. Both are deliberate — the window only needs to slide once it is illegal, and a stale most_common can only make the window look worse than it is, so it can never produce a too-large answer. O(n) time, O(1) space.

6. Minimum Size Subarray Sum — shrinking to minimise#

Problem 209. Shortest subarray with a sum of at least the target.

def min_subarray_len(target, nums):
    left = 0
    window = 0
    best = len(nums) + 1

    for right, value in enumerate(nums):
        window += value

        while window >= target:
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1

    return best if best <= len(nums) else 0

The inversion worth noticing: for a longest window you record the answer after the shrink loop, for a shortest window you record it inside, because the window is legal on the way in and you want the smallest legal one. O(n) time, O(1) space.

7. Permutation in String — a fixed window with a frequency map#

Problem 567. Does the text contain any permutation of the pattern?

from collections import Counter

def check_inclusion(pattern, text):
    size = len(pattern)
    if size > len(text):
        return False

    need = Counter(pattern)
    window = Counter(text[:size])
    if window == need:
        return True

    for right in range(size, len(text)):
        window[text[right]] += 1
        leaving = text[right - size]
        window[leaving] -= 1
        if window[leaving] == 0:
            del window[leaving]
        if window == need:
            return True

    return False

Deleting zero-count keys is what makes the == comparison correct — a Counter with a: 0 is not equal to one without a. O(n) time with a 26-key comparison, O(1) space.

8. Minimum Window Substring — the hard one#

Problem 76. Smallest substring of s containing every character of t, with multiplicity.

from collections import Counter

def min_window(s, t):
    if not t or len(t) > len(s):
        return ""

    need = Counter(t)
    missing = len(t)
    left = 0
    best_left, best_right = 0, 0

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        while missing == 0:
            if best_right == 0 or right + 1 - left < best_right - best_left:
                best_left, best_right = left, right + 1
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

    return s[best_left:best_right]

The trick that makes this manageable is missing: a single integer standing in for "how many required characters are still unmatched", instead of comparing two maps on every step. Counts are allowed to go negative for surplus characters, and only a count returning to a positive value means a genuinely required character has left. O(len(s) + len(t)) time, O(unique characters) space.

When a window is the wrong tool#

Three failure modes, all worth recognising before you have written twenty lines.

Negative numbers with a sum constraint. Growing the window no longer monotonically grows the sum, so "shrink while illegal" discards windows that could have become legal. Use prefix sums with a hash map instead — that is exactly what Subarray Sum Equals K is for, and it is the single most common wrong answer in this pattern.

Subsequences, not substrings. A window is two indices, and two indices can only describe a contiguous run. If elements may be skipped, you are in dynamic programming territory.

The maximum inside the window. A sum updates in O(1) when an element leaves; a maximum does not, because you may have just removed it. Sliding Window Maximum needs a monotonic deque holding indices in decreasing order of value — the monotonic stack pattern applied to a queue.

The four bugs#

In rough order of how often they cost people an interview:

1. Updating the answer in the wrong place. After the shrink loop for a longest window, inside it for a shortest one.
2. left moving backwards. Only ever assign left a larger value. Problem 3's guard exists entirely for this.
3. Forgetting to update the summary when shrinking. Removing nums[left] from the window and forgetting to decrement the count, or vice versa.
4. Off-by-one in the length. It is right - left + 1 when both ends are inclusive. Say it out loud once and it stops being a coin flip.

Work through the eight problems above in order and the pattern stops being something you recognise and becomes something you write. More of them are collected on the sliding window pattern hub, and if you want the pattern in context, the complete pattern map shows where it sits relative to two pointers and prefix sums.

If you would like a second pair of eyes during the interview itself, Stealth Interview is a desktop app for macOS and Windows that reads the problem from a screenshot and works through the approach, the code and the complexity with you, while staying invisible to screen sharing.