The Sliding Window Algorithm: The Pattern That Turns O(n²) into O(n) Overnight

Back with another one in my series where I break down coding patterns that gave me a hard time. This time, I'm tackling the sliding window algorithm, a data structure technique that I avoided for way too long. I'm a little embarrassed about how long I resisted learning it properly.

I Was Writing Nested Loops Like It Was 2015

For months, I had this habit. Every time a problem said "find the maximum sum of k consecutive elements" or "find the longest substring with at most two distinct characters," I'd write two nested loops. Outer loop for the starting position, inner loop to process the window. It worked. It was correct. And it was slow enough to time out on every large test case.

The frustrating part? I knew there was a better way. I'd seen "sliding window" in problem tags on LeetCode. But I kept thinking it was some clever trick that only applied to a handful of problems. I didn't realize it was a foundational pattern that shows up everywhere.

What Actually Confused Me

My confusion wasn't about the concept. "Slide a window across the array" makes sense as a sentence. My confusion was about the mechanics. Specifically:

When do I expand the window? When do I shrink it? How do I know when the window is "valid"? And what exactly am I tracking as the window moves?

Every tutorial I read would jump straight into the code. "Maintain two pointers, left and right." But nobody explained the decision framework. When I looked at a new problem, I couldn't figure out which flavor of sliding window to apply. Fixed-size? Variable-size? What's the invariant?

That's what I want to break down here.

Two Flavors of Sliding Window (and They Cover 90% of Problems)

The first thing that clicked for me was realizing there are really only two types of sliding window problems. Once you know which type you're looking at, the template practically writes itself.

Fixed-Size Window

The problem gives you the window size. "Find the maximum sum of k consecutive elements." "Find the average of every contiguous subarray of length k."

The logic is dead simple. Given an array of integers, you build the first fixed size window by processing elements 0 through k-1. Then as the window slides forward, you grow it by adding each new element to your running total and remove the element that just fell out of the window (the one at position i-k). The function should return the maximum sum found across all windows.

def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

That's it. One pass. O(n) time. The nested loop version would compute each window sum from scratch, which is O(n*k). For k = 1000 and n = 100,000, that's the difference between 100,000 operations and 100,000,000 operations.

Variable-Size Window

This is where the window algorithm gets interesting. The problem doesn't give you a window size. Instead, it gives you a condition to satisfy. "Find the longest subarray or substring with at most k distinct characters." "Find the smallest subarray with sum greater than or equal to target." You need to find subarrays of size that satisfy a given condition.

The template looks like this:

def longest_substring_k_distinct(s, k):
    char_count = {}
    left = 0
    max_length = 0

    for right in range(len(s)):
        # Expand: add the new character
        char_count[s[right]] = char_count.get(s[right], 0) + 1

        # Shrink: while the window violates the condition
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

        # Update the answer
        max_length = max(max_length, right - left + 1)

    return max_length

The right pointer always moves forward, one step at a time. The left pointer only moves when the window condition is violated. You never move left backward. You never move right backward. This is what gives you O(n). Every element enters the window exactly once and leaves exactly once.

The Decision Framework I Wish Someone Had Given Me

After solving about 15 sliding window problems, I noticed a pattern in how I was deciding which approach to use. Here's the framework I built for myself:

The difference between "longest" and "shortest" problems confused me for a while. In "longest" problems, you update the answer outside the while loop (after shrinking to restore validity). In "shortest" problems, you update inside the while loop (each valid shrink might be the answer).

# Shortest subarray with sum >= target
def min_subarray_len(target, nums):
    left = 0
    current_sum = 0
    min_length = float('inf')

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

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

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

Notice the answer update is inside the while loop here. That's the key difference from the "longest" variant.

Sliding Window vs Two Pointers: They're Cousins, Not Twins

I used to think sliding window and two pointers were the same thing. They're not. They share the "two index variables" mechanic, but the intent is different.

Two pointers work on sorted data (or data with some ordering property). One pointer starts at the beginning, one at the end, and they move toward each other. Think: "find two numbers that sum to target" in a sorted array.

Sliding window works on contiguous subarrays or substrings. Both pointers start at the beginning and move in the same direction. The window between them represents a contiguous chunk of the input.

The confusion makes sense because they look similar in code. But if you see "subarray" or "substring" in the problem, think sliding window. If you see "pair" or "sorted array," think two pointers.

The Mistake That Cost Me 45 Minutes in a Mock Interview

I was working on "Minimum Window Substring" (LeetCode 76, and yes, it's a hard). The problem asks: given two strings s and t, find the minimum window in s that contains all characters of t.

I set up my sliding window correctly. I had a frequency map for t. I had a frequency map for the current window. I was expanding right and shrinking left. But my solution was O(n * m) instead of O(n) because every time I moved a pointer, I was comparing the entire frequency maps.

The fix was tracking a "formed" counter. Instead of comparing maps, I tracked how many characters in t had been fully satisfied in the current window. When formed == required, the window was valid. Adding or removing a character only updates one counter, not the whole map.

def min_window(s, t):
    from collections import Counter

    t_count = Counter(t)
    required = len(t_count)
    formed = 0
    window_counts = {}

    left = 0
    min_len = float('inf')
    min_start = 0

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

        if char in t_count and window_counts[char] == t_count[char]:
            formed += 1

        while formed == required:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left

            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in t_count and window_counts[left_char] < t_count[left_char]:
                formed -= 1
            left += 1

    return s[min_start:min_start + min_len] if min_len != float('inf') else ""

Why O(n) and Not O(n²)?

This tripped me up until I thought about it in terms of pointer movements. In a sliding window solution, the right pointer moves forward n times total. The left pointer also moves forward at most n times total (it can never go past right, and it never goes backward). So the total number of operations is at most 2n, which is O(n).

Compare this to the nested loop approach where for each starting position (n positions), you might scan up to n elements. That's O(n²).

The sliding window reuses computation from the previous position. Instead of recalculating the sum of a subarray from scratch, you adjust what changed: one element entered, maybe one element left. This is the same principle behind amortized analysis. Individual operations might vary, but the total work across all operations is bounded.

Five Problems to Practice (In This Order)

If you're just starting with this sliding window coding pattern, I'd suggest this progression:

Each problem builds on the previous one. Don't skip ahead. You can find all of these sliding window problems on LeetCode and practice them in order on Levelop's coding patterns track.

Where This Fits in the Bigger Picture

Sliding window is one of about 12 core patterns that cover the majority of coding interview problems. If you've been reading this series, you've already seen how dynamic programming works as state transitions and the DP template that handles most problems. Sliding window is completely different from DP in approach, but they share one thing: once you see the pattern, problems that seemed impossible become mechanical.

If you're prepping for coding interviews in 2026, the sliding window algorithm is non-negotiable. It shows up at every company, at every level, and it's one of the easiest patterns to learn once you have the right mental model.

I've been working through these patterns on Levelop, and the sliding window module was one that clicked fast once I stopped overcomplicating it.