Sliding Window Algorithm: Coding Interview Guide + Templates

The Sliding Window Algorithm: A Coding Interview Guide (Fixed + Variable Templates)

The sliding window is a technique for problems that ask about a contiguous run of elements — a subarray or substring — where a brute-force scan of every window is O(n·k) or O(n²). By moving two pointers that bound a window and updating a running summary incrementally, you turn that into a single O(n) pass. It's one of the highest-leverage patterns to recognize because it collapses a whole class of "longest/shortest/maximum substring or subarray" questions into two short templates.

This guide gives you the recognition signal, the fixed-size and variable-size templates with runnable Python, when to grow vs shrink the window, complexity, and the edge cases that fail test cases.

When it applies (and when it doesn't)

Reach for a sliding window when all of these hold:

• The data is a linear sequence (array or string).
• You care about a contiguous block (subarray/substring), not an arbitrary subset or subsequence.
• You're optimizing something over that block — longest/shortest length, max/min sum, a count, or a "does a window satisfying X exist" check.

It does not apply when order can be rearranged, when elements needn't be adjacent (that's often two-pointers on a sorted array, or dynamic programming), or when negative numbers break the monotonic "shrinking helps" assumption for sum-threshold problems (a prefix-sum + hashmap is usually the fix there).

Two kinds of window

Almost every sliding-window problem is one of two shapes. Identify which one before you write code.

1. Fixed-size window — the width k is given. You add the entering element, remove the leaving element, and read off the answer once per step. (e.g. "maximum sum of any subarray of size k," "moving average of the last k readings.")
2. Variable-size window — the width changes to satisfy a constraint. A right pointer expands the window; when the window violates the constraint, a left pointer shrinks it. (e.g. "longest substring without repeating characters," "smallest subarray with sum ≥ target.")

Fixed-size template

def max_sum_subarray(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window = sum(nums[:k])          # first window
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # add entering, drop leaving
        best = max(best, window)
    return best

The whole idea is the incremental update + nums[right] - nums[right - k]: you never re-sum the window, so each step is O(1).

Variable-size template

def longest_unique_substring(s):
    seen = {}                       # char -> last index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # shrink past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)  # current window size
    return best

The pattern is always: expand right every iteration; while the window is invalid, advance left; record the answer. The seen[ch] >= left guard is the classic gotcha — a character last seen before the current window's left edge is not actually a duplicate inside the window.

Grow or shrink? The decision that defines the variable window

For "longest valid window" problems you record the answer when the window is valid (after shrinking). For "shortest valid window" problems (e.g. minimum-length subarray with sum ≥ target) you record the answer while shrinking, because each shrink that keeps it valid gives a smaller candidate.

Complexity

Both templates are O(n) time — each pointer moves forward at most n times, so even the nested while shrink loop is amortized O(1) per step, not O(n²). Space is O(1) for numeric windows, or O(k) / O(charset) when you track a hashmap or frequency table of the window's contents. Saying "both pointers only move right, so it's linear" is the explanation interviewers want.

Variations you'll see

• Maximum/average over a fixed window — running sum; the sliding-window moving average is the canonical version.
• Longest substring with at most K distinct characters — variable window + a frequency map; shrink when distinct count exceeds K.
• Minimum window substring — variable window + a need/have count of required characters.
• Window median / order statistics — a fixed window plus a balanced structure (two heaps), as in compute the sliding-window median.
• Streaming / circular windows — fixed window over a stream, like the circular sliding-window ratio tracker.

Common mistakes that fail test cases

• Re-computing the window from scratch. If you sum(nums[left:right+1]) inside the loop, you've rebuilt the O(n²) you were trying to avoid. Update incrementally.
• The stale-index bug. In the longest-unique-substring problem, jumping left to seen[ch] + 1 without the seen[ch] >= left check moves left backward and corrupts the window.
• Off-by-one on window size. Current width is right - left + 1. Mixing inclusive/exclusive bounds is the most common silent error.
• Assuming shrinking always helps. With negative numbers, a longer window can have a smaller sum, so the "shrink while sum ≥ target" logic breaks — reach for prefix sums + a hashmap instead.
• Forgetting to update the answer at the right moment. Longest-window problems update after the window is valid; shortest-window problems update during shrinking. Putting it in the wrong place returns a value that's off by one window.

FAQ

What's the difference between sliding window and two pointers? Sliding window is a specialized two-pointer pattern where both pointers move in the same direction and the region between them (the window) is the thing you're measuring. General two-pointer problems (e.g. pair-sum on a sorted array) often move pointers toward each other and care about the elements at the pointers, not the span between them.

How do I know whether to use a fixed or variable window? If the problem hands you the window width k, it's fixed. If the width is whatever satisfies a constraint ("longest," "shortest," "at most K distinct"), it's variable.

Why is the time complexity O(n) and not O(n²) despite the inner while loop? The left pointer only ever moves forward and never passes the right pointer, so across the whole run it advances at most n times total. That makes the shrink work amortized O(1) per step.

Can sliding window handle negative numbers? For fixed windows, yes. For variable windows driven by a sum threshold, negatives break the monotonic assumption that shrinking lowers the sum — use prefix sums with a hashmap (or a deque for min/max) instead.

What data structure tracks the window's contents? A hashmap or array frequency table for "distinct/count" constraints, a running sum for numeric sums, and a monotonic deque or two heaps for window min/max/median.