title: "The Sliding Window Technique: From O(n²) to O(n) in One Idea" slug: what-is-sliding-window description: A beginner-friendly explanation of the sliding window technique, the intuition, how fixed and variable windows differ, time and space complexity, and how to recognize it in interview problems. tags: [dsa, algorithms, interview-prep, leetcode] date: 2026-06-04

The Sliding Window Technique: From O(n²) to O(n) in One Idea

You have an array and a question about a contiguous piece of it. The brute-force answer writes itself: a nested loop, check every subarray, track the best result. It works. It also gets you rejected.

The sliding window technique replaces that nested loop with a single pass. Same answer, O(n) instead of O(n²). The intuition takes about two minutes to absorb. Getting fluent with both the fixed and variable variants takes a bit longer, but that's what this post is for.

Why the Nested Loop Is Slow

Say you want the maximum sum of any contiguous subarray of length 3 in this array:

[2, 1, 5, 1, 3, 2]

The brute-force approach checks every starting index and sums the next three elements:

def max_sum_brute(nums: list[int], k: int) -> int:
    n = len(nums)
    max_sum = float('-inf')
    for i in range(n - k + 1):
        window_sum = 0
        for j in range(i, i + k):
            window_sum += nums[j]
        max_sum = max(max_sum, window_sum)
    return max_sum

For k = 3 and an array of length 6, that's roughly 12 additions. For an array of length 10,000, it's closer to 30,000,000 additions. The interviewer's expression doesn't change. It's already changed.

You don't need to add 1, 5, and 1 again. When you move from [2, 1, 5] to [1, 5, 1], you're adding 1 and dropping 2. You already know the sum of the middle three. Recomputing it every step is like reintroducing yourself to someone at every sentence because you're worried they forgot your name.

The Core Idea: Slide, Don't Restart

The sliding window insight is this: when a window moves one step to the right, you add the new element on the right and subtract the element that just fell off the left.

[2, 1, 5, 1, 3, 2]
 ^-----^              window = [2, 1, 5], sum = 8
    ^-----^           slide: +1, -2 → sum = 7
       ^-----^        slide: +3, -1 → sum = 9  ← max
          ^-----^     slide: +2, -5 → sum = 6

One addition, one subtraction per step. O(n) total.

def max_sum_sliding(nums: list[int], k: int) -> int:
    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

Same answer. No nested loop. The window slides forward by adding the incoming element and dropping the outgoing one. That's it.

Fixed-Size vs Variable-Size: The Two Sliding Window Variants

Most sliding window problems fall into one of two shapes.

Fixed-size window

The window size k is given. You slide it across the array, updating in O(1) at each step.

Signal: "Find the maximum/minimum/average of every subarray of length k."

The pattern above is the template. Initialize with the first k elements, then slide.

Variable-size window

The window size isn't fixed, it expands and contracts based on a condition. A left pointer and a right pointer define the window. The right pointer always moves forward. The left pointer moves forward only when the window violates the condition.

Classic example: longest substring without repeating characters.

def length_of_longest_substring(s: str) -> int:
    char_count = {}
    left = 0
    max_length = 0

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

        while char_count[char] > 1:
            left_char = s[left]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            left += 1

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

    return max_length

The window [left, right] always contains only unique characters. When right adds a duplicate, left moves right until the duplicate is gone. Every character enters the window once (when right passes it) and leaves the window at most once (when left passes it). That's O(n).

Signal: "Find the longest/shortest subarray/substring satisfying some condition."

Time and Space Complexity

Time: O(n) for both variants.

The key invariant: each element enters the window exactly once and leaves the window at most once. Even in the variable-size case, the left pointer only moves forward, it never rewinds. So across the entire algorithm, the left pointer makes at most n total moves. Two pointers, n moves each, O(n) total.

Space: O(1) for fixed-size windows. You keep a running value (sum, count, whatever) and update it at each step. No auxiliary data structure.

Space: O(k) for variable-size windows, where k is the number of distinct elements in the window at its largest. You need a hash map or array to track what's inside. For ASCII strings that's a fixed ceiling of 128 entries, effectively O(1). For general inputs it scales with window diversity.

How to Recognize a Sliding Window Problem

The pattern shows up when a problem asks about a contiguous subarray or substring and you can maintain the answer incrementally.

Concrete signals:

The word "subarray" or "substring" appears
The question asks for the longest, shortest, maximum, or minimum of something contiguous
There's a constraint that can be checked locally: "sum ≤ k", "at most k distinct characters", "contains all characters of t"
Brute force is O(n²) or O(n³) and the constraint is n up to 10^5 (a strong hint that O(n) is expected)

When you see these, ask yourself: if I fix the right boundary and move it one step, can I update my answer in O(1) or O(log n)? If yes, sliding window is likely the right tool.

A useful distinction: two pointers and sliding window look similar, but they're solving different shapes of problem. Two pointers typically works on sorted arrays and moves both pointers toward each other. Sliding window always moves the right pointer forward and has a condition that controls the left pointer.

A tweet listing silly 2026 interview tasks, Wordle, monkeytype, favourite YouTube video, as better tests than LeetCode

If only. The actual interview has a string problem, a timer, and someone watching you think.

The Sliding Window Template Worth Memorizing

For variable-size windows, the structure is almost always the same:

def sliding_window_template(s: str) -> int:
    state = {}         # track what's in the window
    left = 0
    result = 0

    for right in range(len(s)):
        # 1. expand: add s[right] to state
        state[s[right]] = state.get(s[right], 0) + 1

        # 2. shrink: move left until window is valid again
        while not is_valid(state):
            state[s[left]] -= 1
            if state[s[left]] == 0:
                del state[s[left]]
            left += 1

        # 3. update result with current valid window
        result = max(result, right - left + 1)

    return result

Swap in your validity condition and your result-update logic. The skeleton stays the same.

For fixed-size windows, the skeleton is simpler: initialize the first window, then slide with window_value += incoming - outgoing.

Common Interview Problems That Use This

The sliding window appears in a predictable set of interview problems. A few worth knowing:

Problem	Window type	What you track
Maximum sum subarray of size k	Fixed	Running sum
Longest substring without repeating characters	Variable	Character counts
Minimum window substring	Variable	Character counts vs target
Longest subarray with sum ≤ k	Variable	Running sum
Fruit into baskets (at most 2 distinct)	Variable	Element counts
Maximum average subarray of size k	Fixed	Running sum

The 12 sliding window LeetCode problems that cover every interview variation are worth working through once you have the template down. And if you're getting the mechanics but struggling to identify when to apply the pattern, reading the problem signals before you code will save you more time than grinding more problems.

The `if`/`while` Bug That Everyone Makes Once

The most common error with variable-size windows: moving the left pointer too far.

When the window becomes invalid, you need to shrink it just enough to make it valid again, not until it's maximally small. The while loop in the template handles this correctly, it stops the moment the window is valid. Replacing while with if breaks the algorithm on inputs where you need to shrink by more than one step.

# Wrong: only shrinks by one step
if not is_valid(state):
    remove(s[left])
    left += 1

# Right: shrinks until valid
while not is_valid(state):
    remove(s[left])
    left += 1

One character. The difference between O(n) and a wrong answer. Depending on the interviewer, also the difference between an offer and a rejection email that lands in your spam folder three weeks later.

Watching CI/CD run 1800 tests for a 1-line change that also turns out to be in a comment

if to while is also a one-line change. No pipeline involved. The consequences are just as real.

Putting It Together

The sliding window technique works because contiguous problems have a monotonic structure: if you know the answer for a window, moving the window one step is an incremental update, not a full recomputation.

The fixed-size variant is mechanical once you see it. The variable-size variant has more moving parts, but the template absorbs most of the complexity. Once you internalize the expand-shrink-update loop, the pattern snaps into place across dozens of problems.

If you want to practice recognizing these patterns under time pressure with real feedback, SpaceComplexity runs voice-based mock interviews where you work through problems like these while explaining your thinking out loud, the part that actually determines whether you get the offer.

The algorithm is simple. The skill is pattern recognition fast enough that you're already thinking about edge cases while the interviewer finishes reading the problem. That part takes reps.