The Sliding Window Technique: A Pattern That Solves Dozens of Problems

Sliding window is one of those techniques where once you see it, you start noticing it everywhere. The core idea: instead of recalculating something from scratch for every subarray or substring, maintain a "window" that you slide across the data, updating your answer incrementally.

It turns O(n*k) brute force into O(n). That's the whole pitch.

Fixed-Size Window

The simplest version. You have an array, and you need the maximum (or minimum, or average) of every contiguous subarray of size k.

Problem: Maximum sum of any subarray of size k.

Brute force: for each starting index, sum the next k elements. That's O(n*k).

Sliding window: compute the first window's sum. Then slide: subtract the element leaving the window, add the element entering.

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1

# compute first window
    window_sum = sum(arr[:k])
    max_sum = window_sum

# slide
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

return max_sum

Each element enters the window once and leaves once. O(n) total. The key insight: you don't recompute the whole sum — you adjust it by the two elements at the edges.

Variable-Size Window

This is where it gets more interesting. The window size isn't fixed — it grows and shrinks based on some condition.

The template looks like this:

left = 0
for right in range(len(arr)):
    # expand: add arr[right] to window state

while window_is_invalid():
        # shrink: remove arr[left] from window state
        left += 1

# update answer (window is valid here)

Two pointers, both moving left to right, never moving backward. Each pointer traverses the array at most once, so it's O(n) even though there's a nested loop.

Problem: Smallest Subarray with Sum >= Target

Given an array of positive integers and a target sum, find the length of the shortest contiguous subarray whose sum is at least target.

def min_subarray_len(target, nums):
    left = 0
    current_sum = 0
    min_len = float('inf')

for right in range(len(nums)):
        current_sum += nums[right]

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

return min_len if min_len != float('inf') else 0

The right pointer expands the window until the sum meets the target. Then the left pointer shrinks it as much as possible while the condition still holds. At each valid state, we check if it's the shortest window we've seen.

Problem: Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring with all unique characters.

def length_of_longest_substring(s):
    char_index = {}
    left = 0
    max_len = 0

for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        char_index[s[right]] = right
        max_len = max(max_len, right - left + 1)

return max_len

Here the "window state" is a hash map tracking the last index of each character. When we see a duplicate, we jump left past the previous occurrence. No inner while loop needed because we jump directly instead of incrementing one by one.

How to Recognize Sliding Window Problems

Look for these signals:

1. Contiguous sequence — the problem asks about subarrays or substrings (not subsequences — those are usually DP).

1. Optimization over a range — "maximum," "minimum," "longest," "shortest" of some contiguous chunk.

1. A constraint that can be checked incrementally — sum exceeds a threshold, all characters unique, at most k distinct characters. If you can update the constraint check in O(1) as the window expands or shrinks, sliding window works.

1. Positive values or monotonic properties — for the "shrink when invalid" logic to work, expanding the window should move you in one direction (e.g., increasing sum) and shrinking should move you in the other. If elements can be negative, the sum can go up or down unpredictably, and the shrinking step breaks. (Negative values usually mean you need prefix sums or DP instead.)

Common Variations

At most k distinct characters — maintain a frequency map. When distinct count exceeds k, shrink from the left until you're back to k.

def longest_with_k_distinct(s, k):
    freq = {}
    left = 0
    max_len = 0

for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1

while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1

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

return max_len

Maximum of each window of size k — this uses a deque (monotonic queue) to track the max efficiently. Slightly different flavor, but still a sliding window.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, front is always the max
    result = []

for i in range(len(nums)):
        # remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

# remove smaller elements (they'll never be the max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

dq.append(i)

if i >= k - 1:
            result.append(nums[dq[0]])

return result

The deque maintains a decreasing order of values. The front is always the current window's maximum. Elements that can never be useful get discarded.

Minimum window substring — given strings s and t, find the smallest window in s that contains all characters of t. This combines a frequency map with the expand/shrink template and is considered a hard problem, but the pattern is identical.

The Mental Model

Think of the window as a caterpillar crawling along the array. The right end reaches forward (expand), and the left end catches up (shrink). Both ends only move forward. That forward-only property is what guarantees O(n) — each element is processed at most twice (once when it enters, once when it leaves).

If your brute force is checking all O(n^2) subarrays, ask yourself: can I maintain the answer incrementally as I slide? If yes, you've found a sliding window problem.

You can practice these patterns interactively on CodeUp — start with the fixed-size window problems to build intuition, then move to variable-size. The progression makes the template feel natural rather than memorized.