Master the Sliding Window Technique: Pattern Recognition Guide

The sliding window technique solves a large family of array and string problems in one pass over the input.

What is a Sliding Window?

A window is a contiguous stretch of the input, marked by a left index and a right index. Alongside the two indices you keep a small summary of what is inside, such as a running sum or a count of each character. The technique works whenever that summary can be updated cheaply as one element enters on the right and another leaves on the left.

Fixed Size Window

Use this when the problem fixes the length, as in "the largest sum of any k consecutive elements."

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Time complexity is O(n).

Space complexity is O(1).

Take arr = [2, 1, 5, 1, 3, 2] and k = 3. The four window sums are 8, 7, 9, and 6, so the answer is 9. The element leaving is always arr[i - k], exactly k places behind the one arriving, so check that index by hand on the first slide. If the array can be shorter than k, the function returns the sum of the whole array, so ask what the problem expects.

When the summary cannot be undone

A running sum works because subtraction undoes an addition. A running maximum has no such undo, since nothing in a single number tells you the new largest once the old one leaves. For "the maximum of every window of size k," keep a deque (a queue you can push and pop at both ends) of indices whose values decrease from front to back.

from collections import deque

def max_of_each_window(nums, k):
    dq = deque()  # indices; their values decrease from front to back
    result = []
    for right, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(right)
        if dq[0] <= right - k:
            dq.popleft()
        if right >= k - 1:
            result.append(nums[dq[0]])
    return result

After each step, the front of the deque holds the window's maximum. A new element pops every smaller value off the back, because none of those can be the maximum while the newer, larger one is still in the window. Each index enters and leaves the deque at most once, so the pass stays O(n) even when one step pops several items.

Variable Size Window

Use this when the length is part of the answer, as in "the longest substring without a repeated character."

def longest_substring_without_repeating(s):
    char_map = {}
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        if s[right] in char_map:
            left = max(left, char_map[s[right]] + 1)
        
        char_map[s[right]] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

After every step, the window from left to right contains no repeated character. When the new character was last seen inside the window, left jumps to one past that earlier position. The max() call matters because the dictionary still holds positions from before left. On "abba", when right reaches the final "a", its stored position is 0. Without max(), left would move back from 2 to 1, and the window "bba" would report a length of 3 instead of the correct 2.

Grow, then shrink

Most variable windows follow one template. Advance right to take in a new element, then advance left while the window breaks the rule. For "shortest" questions, shrink while the window still qualifies and record the length each time.

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

With target = 7 and nums = [2, 3, 1, 2, 4, 3], the shortest window found is [4, 3], so the function returns 2. The nested while loop still leaves this O(n), because right moves forward n times and left only ever moves forward, so the two indices take at most 2n steps between them.

This template needs every number to be positive, so that adding an element raises the sum and removing one lowers it. On [1, -1, 5] with a target of 5, the window grows to the whole array, drops the 1, sees a sum of 4, and stops with an answer of 3, even though [5] alone has length 1. Problems that allow negatives, such as counting subarrays that sum to exactly k, use prefix sums and a hash map, the same lookup that solves Two Sum in one pass.

How to recognize a window problem

The statement usually says contiguous, consecutive, subarray, or substring, and asks for a longest, a shortest, a maximum, or a count. A subsequence may skip elements and a window cannot, so "subsequence" problems usually call for dynamic programming instead. The rule you check must also change in one direction as the window grows, like the positive sums above or "at most k distinct characters."

A sliding window is a two pointer method whose pointers both move right. The Two Sum walkthrough covers the other common shape, where the pointers close in from both ends of a sorted array.

Problems to practice

• Maximum Average Subarray: a fixed window with a running sum.
• Sliding Window Maximum: a fixed window with the deque.
• Longest Substring Without Repeating Characters: a variable window with a map of last positions.
• Minimum Size Subarray Sum: grow, then shrink, on positive numbers.

For a routine to practice spotting these problems, see LeetCode interview tips.