Sliding Window

What is sliding window?

The sliding window technique processes a contiguous subarray or substring by advancing two pointers - start and end - rather than recomputing the window from scratch each time. The window slides forward, and the cost of each slide is O(1) for the update, making the total O(n) instead of the O(n²) of a nested loop.

Two variants cover nearly all interview problems. The fixed-size window has a length given by the problem (always equal to k). You expand by adding the element at end, and when the window reaches size k, record the result then shrink by removing the element at start and advancing start. The variable-size window grows until a constraint is violated, then shrinks until the constraint is satisfied again.

The key invariant for variable windows: at all times, [start, end] satisfies the problem's constraint. When adding nums[end] breaks the constraint, move start forward until it is restored. Because start only ever moves forward and never backtracks, the total number of start advances across the entire algorithm is at most n - the nested shrink loop is O(n) amortized, not O(n²).

Different from two pointers in a subtle way: both techniques use two pointers moving in the same direction, but sliding window always centers on the concept of a maintained contiguous window. Two pointers often converges from opposite ends and the constraint is a relationship between two specific values rather than a window aggregate.

Core operations

Key patterns

Fixed-size window

Keep a window of exactly k elements and slide it one step at a time, adding the element that enters and dropping the one that leaves.

When to use - the problem hands you a window size k and asks for a property (max, min, sum, average) of every k-element window. Recomputing each window from scratch is O(n * k); sliding it updates in O(1) per step and collapses that to O(n).

How it works - seed the aggregate once with the first k elements. Each step, add nums[end] and subtract nums[end - k] - the element exiting the back is always exactly k positions behind the one entering, so you never track a separate start. That one add and one subtract per step is why each index is touched a constant number of times, keeping the whole scan O(n).

def max_sum_fixed(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for end in range(k, len(nums)):
        window_sum += nums[end] - nums[end - k]  # slide: add new, remove old
        best = max(best, window_sum)
    return best

Variable-size window (expand/shrink)

Grow the window from the right until a constraint breaks, then shrink it from the left until the constraint holds again.

When to use - the problem asks for the longest or shortest contiguous subarray or substring that satisfies a sum, count, or character condition. The brute-force version checks every start/end pair at O(n²); a window that only ever moves forward answers it in one O(n) pass.

How it works - the invariant is that [start, end] always satisfies the constraint by the end of each outer step. Expand end by one each iteration; when adding nums[end] breaks the constraint, run an inner while loop that advances start until it holds again. For longest-window problems record the length after the shrink (the window is valid then); for shortest-window problems record inside the shrink loop while it is still valid. The nested loop looks O(n²), but start never moves backward, so across the whole run it advances at most n times - every index enters the window once and leaves at most once, which is why it stays O(n).

from collections import defaultdict
 
def longest_without_repeating(s):
    char_count = defaultdict(int)
    start = 0
    best = 0
    for end in range(len(s)):
        char_count[s[end]] += 1
        while char_count[s[end]] > 1:  # window is invalid: duplicate present
            char_count[s[start]] -= 1
            start += 1
        best = max(best, end - start + 1)
    return best

Canonical examples

Maximum average subarray of size k (fixed window)

The naive approach recomputes the sum of k elements for each starting position: O(n * k). The sliding window computes the initial sum once then adjusts by one add and one subtract per step. The key insight: when the window slides right by one position, exactly one element enters the right side and one exits the left side.

Longest substring without repeating characters (variable window)

The window grows until it contains a duplicate character, then shrinks from the left until the duplicate is removed. The frequency map tracks how many times each character appears in the current window. The window is valid when every character count is at most 1.

When to reach for sliding window

• The problem involves a contiguous subarray or substring with a sum, count, or character constraint.
• The problem gives a window of size k and asks for a property of each window - fixed window.
• The problem asks for the longest or shortest subarray satisfying a condition - variable window.
• You see a nested loop that re-scans elements the outer loop already visited - sliding window eliminates the inner scan.
• The problem mentions minimum window containing, permutation in string, or fruit into baskets - all variable sliding window.
• The constraint is monotonic: adding more elements makes the window consistently more or less valid.

Practice problems

• Maximum Average Subarray I - Fixed window; the simplest sliding window problem.
• Longest Substring Without Repeating Characters - Variable window with a character frequency map.
• Permutation in String - Fixed window; compare character frequency snapshots.
• Longest Repeating Character Replacement - Variable window; shrink condition involves the max-frequency character count.
• Minimum Window Substring - Variable minimum window; the hardest sliding window problem.
• Sliding Window Maximum - Fixed window plus a monotonic deque that keeps the running maximum in O(1) per step.