Sliding Window Technique: Turn O(n²) Loops into O(n) in One Pass

You have an array. You want to find the longest subarray satisfying some condition. The obvious solution: try every subarray. That is two nested loops, O(n²), and it will time out on any serious input.

The sliding window technique collapses those two loops into one. The core insight is that you never need to restart from scratch: you maintain a window by moving two pointers, and each element enters and leaves that window exactly once. The total work is O(2n), which is O(n). Every sliding window problem reduces to this same accounting argument.

This post covers both window types (fixed and variable), the expand-and-contract pattern, the monotonic deque variant for window extremes, the "at most k" trick for exact-count problems, and when each flavor applies. Implementations follow in every major language.

Stage 2 is your O(n²) solution hitting the time limit. This post exists so you can skip stage 3.

Two Flavors, One Idea

Sliding window problems split cleanly into two families.

Fixed window: the window size is given. You slide a constant-sized frame across the array, removing the element that drops off the left and adding the element that enters on the right. No decisions about size, just arithmetic.

Variable window: the window size changes based on some validity condition. You expand by moving the right pointer, and when the window breaks a constraint, you contract by moving the left pointer until it is valid again. The window breathes.

Both use the same two-pointer frame. The difference is what drives the left pointer.

How It Works: Fixed Window

Given an array of n numbers, find the maximum sum of any k consecutive elements.

The naive approach computes each window from scratch:

for i in range(n - k + 1):
    total = sum(arr[i:i+k])   # O(k) work per window

That is O(n × k). For n = 10⁶ and k = 500, that is five hundred million operations. LeetCode will show you a red banner in under a second. Your interviewer will politely say "interesting approach, but can you do better?" You will not know why, yet.

The fix: when the window slides right by one position, you add arr[right] and subtract arr[left]. You keep a running sum and update it in O(1).

window_sum = sum(arr[0:k])         # seed the first window
for right in range(k, n):
    window_sum += arr[right] - arr[right - k]
    best = max(best, window_sum)

Each element is touched exactly once. O(n) total, O(1) space.

The fixed window is a special case where left = right - k always. You never need to think about when to shrink; the left pointer is just the right pointer minus a constant.

Fixed window: size k = 3
arr = [2, 1, 5, 1, 3, 2]
        [---]                 sum = 8
           [---]              sum = 7
              [---]           sum = 9  ← best
                 [---]        sum = 6
                    [---]     sum = 6

The window slides one position at a time. One element in, one element out, running sum updated in O(1).

How It Works: Variable Window

The window can grow or shrink, and you have to decide when.

The canonical variable window loop looks like this:

left = 0
for right in range(len(s)):
    # 1. Expand: include s[right] in the window
    add(s[right])

    # 2. Contract: shrink while the window is invalid
    while window_is_invalid():
        remove(s[left])
        left += 1

    # 3. Record: window [left, right] is now valid
    best = max(best, right - left + 1)

The while loop is not a second linear scan. (I know it looks like one. Keep reading.) The left pointer only moves forward. Over the entire run, it advances at most n times total, regardless of how many times the inner loop executes during any single iteration of the outer loop. That is the amortized argument: left moves right at most n times, right moves right at most n times, total work O(2n) = O(n).

Let me trace "Longest Substring Without Repeating Characters" on "abcba":

s = "a b c b a"
     0 1 2 3 4

right=0: window="a", seen={a:1}, len=1
right=1: window="ab", seen={a:1,b:1}, len=2
right=2: window="abc", seen={a:1,b:1,c:1}, len=3
right=3: s[3]='b', seen[b] becomes 2 → invalid
         shrink: remove 'a', left=1, seen={a:0,b:2,c:1}
         still invalid (b:2), remove 'b', left=2, seen={b:1,c:1}
         valid now. window="cb", len=2
right=4: s[4]='a', seen={a:1,b:1,c:1}, window="cba", len=3

best = 3 ("abc" or "cba")

The left pointer jumped from 0 to 2 in one inner loop. It will never revisit index 0 or 1. That is the key: no backtracking, ever.

When left jumps, it is gone. No revisiting. That is the entire reason this is O(n).

The Invariant You Have to Maintain

Every variable sliding window carries an invariant: the window [left, right] always satisfies the problem's validity condition (or you are in the middle of restoring it by contracting).

You have to pick what "invalid" means, and you have to be able to update your state in O(1) when you add or remove an element. If either of those is expensive, sliding window does not apply. Most subarray and substring problems naturally fit: frequency counts update in O(1), sums update in O(1), set membership updates in O(1).

The two questions you need to answer before writing any code:

1. What makes the window invalid?
2. What data structure tracks that condition in O(1)?

Answer those and the rest is mechanical.

Complexity at a Glance

The O(n) bound for the variable window holds because the left pointer starts at 0 and only moves right, so its total displacement across the entire algorithm is at most n. The right pointer also moves at most n positions. Two pointers, each moving at most n steps: O(2n) total work.

This O(n) is tight, not amortized. Unlike a dynamic array that occasionally does O(n) resizes, every pointer move here is O(1). There are no expensive outliers hiding in the average. The bound holds in the worst case.

When to Record the Answer

There is one choice that trips people up more than any other.

"Find the longest X": expand aggressively, shrink only when the window breaks the constraint, record the answer after shrinking.

"Find the shortest X": expand until the constraint is satisfied, then shrink as much as possible while keeping it satisfied, record at the point of maximum contraction.

For "smallest window containing all characters of string T," you expand until you have all required characters, shrink while still valid, record each valid window, then expand again. The record step happens inside the shrink loop, not outside it.

# Longest: record outside the shrink loop
while invalid():
    remove(left); left += 1
best = max(best, right - left + 1)

# Shortest: record inside the shrink loop
while valid():
    best = min(best, right - left + 1)
    remove(left); left += 1

Getting this backwards gives you wrong answers that are genuinely baffling to debug. You will add print statements. You will trace through it twice by hand. You will be convinced the logic is fine. It is not. Check where you record.

The "Exactly K" Trick

Some problems ask for subarrays with exactly k distinct elements, exactly k zeros, or some exact count. "Exactly" is hard for sliding window because the validity check is not monotonic: adding an element can make the window switch from invalid to valid to invalid again.

The fix: exactly(k) = atMost(k) - atMost(k - 1).

This looks like a math trick. It is. But it is not pulling a rabbit out of a hat. Count subarrays with at most k elements satisfying the condition (easy, standard shrink-when-over-k pattern), then subtract the count with at most k-1. The difference is exactly k. You call the same helper twice with different limits.

This works because subarrays with at most k X is a superset of at most k-1 X, and their difference is exactly k X:

| atMost(k) | = | exactly k | + | exactly k-1 | + ... + | exactly 0 |
| atMost(k-1) |              = | exactly k-1 | + ... + | exactly 0 |
difference:     = | exactly k |

LeetCode 992 (Subarrays with K Different Integers) and 1248 (Count Number of Nice Subarrays) both reduce to this.

Want the Window Maximum? Use a Monotonic Deque

Standard sliding window tracks sums or counts, which update in O(1). But what if you need the maximum or minimum of the current window? A naive scan is O(k) per window, giving O(nk) overall. A heap brings it to O(n log k). But there is an O(n) solution.

A monotonic deque maintains a decreasing sequence of indices into the window. When you add arr[right], you pop all indices from the back of the deque whose values are less than arr[right] (they can never be the maximum of any future window, since right is newer and larger). Then push right. The front of the deque is always the index of the current window's maximum.

When the window slides, if deque[0] < left, pop from the front (that index has left the window).

arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

right=0: deque=[0]            window=[1]           max=1
right=1: arr[1]=3>arr[0]=1, pop 0. deque=[1]       window=[1,3]         max=3
right=2: arr[2]=-1<arr[1]=3. deque=[1,2]           window=[1,3,-1]      max=3
right=3: arr[3]=-3<arr[2]. deque=[1,2,3]           window=[3,-1,-3]     max=3
right=4: arr[4]=5>everything, pop 3,2,1. deque=[4] window=[-1,-3,5]     max=5
right=5: arr[5]=3<arr[4]=5. deque=[4,5]            window=[-3,5,3]      max=5
right=6: arr[6]=6>arr[5]=3, pop 5. 6>arr[4]=5, pop 4. deque=[6]         max=6
right=7: arr[7]=7>arr[6]. deque=[7]                                      max=7

Each index is pushed exactly once and popped at most once. O(n) total across all windows.

When a new element comes in larger than the back of the deque, those smaller elements are gone. They could never be the max of any future window anyway.

One Structure, Every Language

The implementations below show three patterns: fixed window (max sum of k consecutive elements), variable window (longest substring without repeating characters), and the monotonic deque (sliding window maximum). Pick the one that matches your problem.

from collections import deque

def max_sum_fixed(arr: list[int], k: int) -> int:
    window_sum = sum(arr[:k])
    best = window_sum
    for right in range(k, len(arr)):
        window_sum += arr[right] - arr[right - k]
        best = max(best, window_sum)
    return best


def longest_no_repeat(s: str) -> int:
    seen: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best


def sliding_window_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    result = []
    for right in range(len(nums)):
        while dq and nums[dq[-1]] <= nums[right]:
            dq.pop()
        dq.append(right)
        if dq[0] < right - k + 1:
            dq.popleft()
        if right >= k - 1:
            result.append(nums[dq[0]])
    return result

Where the Sliding Window Technique Applies

Sliding window applies whenever you need to inspect every contiguous subarray or substring and the validity condition can be maintained incrementally.

Optimization over fixed-length windows. Maximum or minimum sum, average, product, count of some property, all across every window of size k. You replace O(nk) brute force with O(n).

Extremal contiguous segments. Longest or shortest subarray satisfying a constraint: sum at most S, at most k distinct characters, at most k zeros, all repeated characters within distance d. These all follow the variable window expand-and-contract template.

Permutation and anagram detection. "Does string T appear as an anagram in string S?" Maintain a frequency map of the current window and compare it to T's frequency map. A single integer satisfied counter tracks how many characters match. O(n) total.

Exact count problems. As covered above, when the constraint is "exactly k," convert it to two "at most" problems.

Window extremes. Maximum or minimum of every window of size k. Monotonic deque gives O(n).

How to Spot a Sliding Window Problem

The primary signal is "contiguous subarray or substring" combined with some aggregate condition. If the problem says "subsequence" or "elements that need not be adjacent," sliding window does not apply. If the problem says "subarray" or "substring" plus anything about sums, counts, or character frequencies, it almost certainly does.

Secondary signals:

• "Longest/shortest/maximum/minimum" combined with "subarray" or "substring"
• "All subarrays of size k"
• "Subarrays with at most / exactly / at least k [X]"
• "Find a permutation of T in S"
• "Minimum window containing all characters of T"
• Time limit implies O(n) or O(n log n), with n up to 10⁶

The validity check must update in O(1) across pointer moves. If the only way to check validity is to re-scan the window, sliding window does not apply.

Worked Example 1: Fruits Into Baskets (LeetCode 904)

Problem: you walk along a row of fruit trees. You have two baskets and can carry one type of fruit per basket. Find the length of the longest subarray containing at most 2 distinct values.

This is "longest subarray with at most k=2 distinct elements." Variable window:

• Expand: add fruits[right] to a frequency map.
• Invalid when: map has more than 2 keys.
• Contract: decrement freq[fruits[left]], remove from map if zero, advance left.
• Record: right - left + 1 after each potential shrink.

The validity check (map size) updates in O(1) per pointer move. O(n) total.

def total_fruit(fruits: list[int]) -> int:
    from collections import defaultdict
    freq: dict[int, int] = defaultdict(int)
    left = 0
    best = 0
    for right in range(len(fruits)):
        freq[fruits[right]] += 1
        while len(freq) > 2:
            freq[fruits[left]] -= 1
            if freq[fruits[left]] == 0:
                del freq[fruits[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

Worked Example 2: Minimum Window Substring (LeetCode 76)

Problem: given strings S and T, find the smallest window in S containing all characters of T.

This is "shortest subarray satisfying a completeness condition." Variable window, but the record step happens inside the shrink loop:

• Build need: frequency map of T.
• Maintain window: frequency map of current window.
• Maintain satisfied: count of character types where window[c] >= need[c].
• Expand until satisfied == len(need) (window contains all characters).
• Then shrink while still satisfied, recording each valid window length.

from collections import Counter

def min_window(s: str, t: str) -> str:
    need = Counter(t)
    window: dict[str, int] = {}
    satisfied = 0
    required = len(need)
    left = 0
    best_start = 0
    best_len = float('inf')

    for right in range(len(s)):
        ch = s[right]
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            satisfied += 1

        while satisfied == required:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left
            leaving = s[left]
            window[leaving] -= 1
            if leaving in need and window[leaving] < need[leaving]:
                satisfied -= 1
            left += 1

    return '' if best_len == float('inf') else s[best_start:best_start + best_len]

The satisfied integer is the invariant. It tells you in O(1) whether the window is complete. Every pointer move updates it in O(1). O(n + |T|) total.

Where People Go Wrong

These mistakes are so common they deserve names.

Forgetting to check the character is in need before updating satisfied. You only care about characters that appear in T. Updating satisfied for every character creates false positives. Your code will think the window is complete when it is not. You will pass 50 test cases and fail on the 51st with an input that has unusual characters.

Recording the answer in the wrong place. For "longest," record after the shrink loop. For "shortest," record inside the shrink loop. Mixing these up gives answers that are genuinely baffling to debug. You will add print statements. You will trace through it twice by hand. You will be convinced the logic is fine. It is not. Check where you record.

Using a set instead of a map when duplicates matter. For "longest substring with at most k distinct characters," you need to know when a character's count drops to zero so you can remove it from your tracking. A set does not track counts. You will shrink the window too early and wonder why.

Accidentally adding an O(k) factor back. Sliding window is O(n) only if the window state updates in O(1). Calling sorted(window) or sum(window) inside the loop adds an O(k) or O(n) factor per step. Maintain the aggregate incrementally: update it on each pointer move, never recompute it from scratch. This is the whole point. If you recompute from scratch, you are back to the brute force you started with.

Quick Reference

• Fixed window: constant size k, left = right - k always, O(n) by updating the running aggregate in O(1)
• Variable window: two pointers, expand by moving right, contract by moving left, each pointer moves at most n positions total
• The amortized O(n) is strict: every element enters once (right pointer) and leaves at most once (left pointer), total 2n moves
• Validity check must update in O(1): sums, frequency maps, counts all qualify
• For "exactly k" constraints, use atMost(k) - atMost(k - 1)
• For window maximum or minimum, use a monotonic deque: O(n) by pushing and popping each index at most once
• Primary recognition signals: "contiguous subarray/substring" plus an aggregate condition on sum, count, or character frequency

If you want to drill these patterns under real interview conditions, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly these problems. You practice explaining the expand-contract logic out loud, which is where most people actually lose points.

For a lighter intro to the sliding window concept, the sliding window algorithm post on this blog walks through the intuition with fewer patterns. If you are working on dynamic programming problems alongside these, the dynamic programming framework covers the same style of pattern recognition for DP.

Further Reading

• Sliding Window Technique - GeeksforGeeks - comprehensive reference with code examples in multiple languages
• Sliding Window Pattern - LeetCode Discuss - community summary of all subarray and substring variants
• Monotonic Queue - Wikipedia - formal treatment of the monotonic queue used for window extremes
• Two Pointer Technique - GeeksforGeeks - the broader family of algorithms that sliding window belongs to
• Sliding Window Maximum (LeetCode 239) - the canonical hard problem demonstrating the monotonic deque