Sliding Window Technique

The sliding window technique lets you examine every contiguous subarray or substring of an array or string without recomputing the same work over and over. Instead of nested loops that check every possible start and end position — costing O(n²) or worse — you maintain a moving window of elements and update a running total, count, or set in O(1) as the window slides forward. It is one of the highest-leverage techniques for array and string problems and shows up constantly in coding interviews under phrasing like "longest substring with…" or "maximum sum subarray of size k".

Overview / How It Works

Picture a strip of paper with numbers written on it, and a cardboard frame of fixed width that you slide across it one number at a time. At each position, instead of adding up everything under the frame from scratch, you subtract the number that just fell out on the left and add the number that just entered on the right. That is the entire idea behind a fixed-size sliding window: maintain a running aggregate (sum, count, max, and so on) for the current window and update it incrementally in O(1) per step instead of recomputing it in O(k) per step.

A window is defined by two pointers, conventionally named left and right (or start/end), that both move forward through the sequence — never backward. That "never backward" property is what makes sliding window fast: each pointer visits each index at most once over the whole run, so total work across the entire scan is O(n), not O(n × window size).

There are two common flavors:

  • Fixed-size window: the width k is given up front (for example, "max sum of any 3 consecutive elements"). Both pointers move together, one step at a time, keeping the width constant.
  • Variable-size (dynamic) window: the width grows and shrinks based on a condition (for example, "shortest subarray with sum at least target" or "longest substring without repeating characters"). The right pointer always expands the window by one each iteration; the left pointer only advances, inside a while loop, when the window violates or over-satisfies the condition you care about.

The insight that keeps the variable-size version O(n) instead of O(n²) is that left, across the entire run of the algorithm, only ever moves forward, and the total number of times it advances across all iterations combined is at most n. Even though there is a while loop nested inside a for loop, the two pointers together perform at most 2n pointer movements in total — the same amortized-cost argument used to analyze the two-pointer technique.

Time and Space Complexity

Pattern Time Space Why
Fixed-size window (width k) O(n) O(1) There are n – k + 1 window positions; each transition does O(1) work (subtract the outgoing element, add the incoming one).
Variable-size window O(n) O(1) to O(k) right advances n times total; left advances at most n times total across the whole run, so combined pointer movement is O(n), not O(n²). Space depends on whether you track just a number (O(1)) or a set/dict of window contents (up to O(k)).
Naive brute force (for comparison) O(n × k) or O(n²) O(1) Recomputes the window’s aggregate from scratch at every starting position instead of reusing the previous window’s work.

The key thing to justify in an interview is why it’s O(n) despite the nested loop: the outer for loop runs n times, but the inner while loop’s total iterations across the entire function call are bounded by n, because left can only move forward a total of n times before hitting the end of the array. Multiplying "n outer iterations" by "n inner iterations" would overcount — the correct analysis sums the inner loop’s work across all outer iterations, which telescopes to O(n).

Examples

Example 1: Maximum sum of a fixed-size window

The classic introduction to sliding window: find the maximum sum of any k consecutive elements. The brute-force approach recomputes the sum of each window from scratch (O(n × k)); the sliding window approach computes the first window’s sum once, then updates it in O(1) as the window slides.

def max_sum_subarray(nums: list[int], k: int) -> int:
    if len(nums) < k:
        raise ValueError("k cannot be greater than length of nums")
    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

nums = [2, 1, 5, 1, 3, 2]
k = 3
result = max_sum_subarray(nums, k)
print(f"Max sum of window size {k}: {result}")

Output:

Max sum of window size 3: 9

The first window [2, 1, 5] sums to 8. Sliding one step right, we subtract the outgoing 2 and add the incoming 1 (window [1, 5, 1], sum 7). Sliding again subtracts 1 and adds 3 (window [5, 1, 3], sum 9 — the new max). Sliding once more subtracts 5 and adds 2 (window [1, 3, 2], sum 6). The maximum across all windows is 9.

Example 2: Smallest subarray with a sum at least target

This is a variable-size window: we don’t know the window’s width ahead of time. We grow the window by moving right forward, and whenever the current window’s sum is already large enough, we try to shrink it from the left to find a tighter answer, recording the length each time the condition holds.

def smallest_subarray_with_sum(nums: list[int], target: int) -> int:
    left = 0
    window_sum = 0
    min_length = len(nums) + 1
    for right in range(len(nums)):
        window_sum += nums[right]
        while window_sum >= target:
            min_length = min(min_length, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return min_length if min_length <= len(nums) else 0

nums = [2, 1, 5, 2, 3, 2]
target = 7
result = smallest_subarray_with_sum(nums, target)
print(f"Smallest subarray length with sum >= {target}: {result}")

Output:

Smallest subarray length with sum >= 7: 2

The window grows until its sum first reaches 8 at [2, 1, 5] (indices 0-2), giving a candidate length of 3. Shrinking from the left drops the sum to 6, below target, so shrinking stops. The window keeps growing; by the time right reaches index 3 the sum is 8 again ([1, 5, 2]), and shrinking finds a length-2 window [5, 2] summing to 7. No shorter window exists, so the final answer is 2.

Example 3: Longest substring without repeating characters

Here the "window" is a substring, and the condition is "no duplicate characters inside the window". Instead of a running sum, we track the most recent index at which each character was seen, letting us jump left directly past a duplicate instead of removing characters one at a time.

def length_of_longest_substring(s: str) -> int:
    char_index: dict[str, int] = {}
    left = 0
    max_length = 0
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
    return max_length

text = "abcabcbb"
result = length_of_longest_substring(text)
print(f"Length of longest substring without repeating characters: {result}")

Output:

Length of longest substring without repeating characters: 3

The window grows cleanly through a, b, c (length 3). At index 3 we see a again, whose last seen index (0) is inside the current window, so left jumps to 1. The same pattern repeats for the next few characters, and the window length never exceeds 3 for the rest of the string, so the longest duplicate-free substring is "abc", length 3.

How It Works Step by Step

Let’s trace Example 2 in detail on nums = [2, 1, 5, 2, 3, 2] with target = 7, watching left, right, and window_sum at every step.

right window_sum after add Action left after min_length
0 2 2 < 7, no shrink 0 7 (none yet)
1 3 3 < 7, no shrink 0 7 (none yet)
2 8 8 ≥ 7: record length 3, shrink to sum 6 1 3
3 8 8 ≥ 7: record length 3 (no better); shrink to 7, still ≥ 7: record length 2; shrink to 2 3 2
4 5 5 < 7, no shrink 3 2
5 7 7 ≥ 7: record length 3 (no better); shrink to 5 4 2

Notice how at right = 3 the inner while loop runs twice in a single outer iteration — that’s exactly why the algorithm needs a while, not an if: one pass isn’t always enough to restore the invariant. By the end, min_length settled at 2, matching the printed output.

Common Mistakes

Mistake 1: Off-by-one in the window length

A window spanning indices left through right inclusive has right - left + 1 elements, not right - left. Forgetting the + 1 silently undercounts every window by one, which is easy to miss because the code still runs without error — it just reports a slightly-too-short answer.

for right in range(len(s)):
    while s[right] in window_set:
        window_set.remove(s[left])
        left += 1
    window_set.add(s[right])
    max_length = max(max_length, right - left)  # BUG: undercounts window length by one

Corrected:

for right in range(len(s)):
    while s[right] in window_set:
        window_set.remove(s[left])
        left += 1
    window_set.add(s[right])
    max_length = max(max_length, right - left + 1)  # length is inclusive, so add 1

Mistake 2: Using if instead of while to shrink the window

When a single new element can push the window’s condition from "not satisfied" to "satisfied by a lot", one shrink step is not always enough to find the tightest window — you may need to shrink several times in the same outer iteration (as seen at right = 3 in the step-by-step trace above). Using if only shrinks once and misses shorter valid windows.

for right in range(len(nums)):
    window_sum += nums[right]
    if window_sum >= target:  # BUG: only shrinks once, even if more shrinking is needed
        min_length = min(min_length, right - left + 1)
        window_sum -= nums[left]
        left += 1

Corrected:

for right in range(len(nums)):
    window_sum += nums[right]
    while window_sum >= target:  # keep shrinking until the window no longer satisfies the condition
        min_length = min(min_length, right - left + 1)
        window_sum -= nums[left]
        left += 1

A third pitfall worth naming even without a code sample: reaching for a fresh sum(nums[left:right + 1]) or set(s[left:right + 1]) inside the loop "just to be safe". That silently turns an O(n) sliding window back into an O(n × k) brute force, defeating the entire point of the technique — always update the running aggregate incrementally instead of recomputing it from the raw slice.

Best Practices

  • Reach for sliding window whenever a problem asks about a contiguous subarray or substring with a max/min/count/target condition — if the elements don’t need to stay adjacent, this is the wrong technique (look at hashing or sorting instead).
  • Decide up front whether the window is fixed-size or variable-size; that decision determines whether both pointers move in lockstep or whether left lives inside a while loop.
  • Always update the running aggregate incrementally (add the incoming element, remove the outgoing one) rather than recomputing it from a slice each iteration — that’s what makes the technique O(n).
  • For character/element frequency conditions, use collections.Counter or a plain dict to track counts inside the window instead of scanning the window on every step.
  • When the condition can flip from satisfied to unsatisfied more than once per outer step, shrink with a while loop, not an if.
  • Watch window length arithmetic closely: it’s right - left + 1, and it’s easy to be off by one, especially when translating from 0-indexed loop variables to a human-readable length.
  • Trace a small example by hand (5-8 elements) before trusting the code on the full input — sliding window bugs are usually invisible until you check a specific index.

Practice Exercises

Exercise 1: Maximum average subarray

Given a list of integers nums and an integer k, find the maximum average value of any contiguous subarray of length k. Reuse the fixed-size window pattern from Example 1, but divide the best sum by k at the end. For nums = [1, 12, -5, -6, 50, 3] and k = 4, the expected output is 12.75.

Exercise 2: Longest subarray with at most two distinct values

Given a list of integers, find the length of the longest contiguous subarray that contains at most two distinct values. Hint: track counts of each value currently in the window with a dict, and shrink from the left whenever the dict has more than two keys. For nums = [1, 2, 1, 2, 3, 1, 2], the expected output is 4 (the subarray [1, 2, 1, 2]).

Exercise 3: Minimum window containing all target characters

Given a string s and a string target, find the length of the smallest contiguous substring of s that contains every character of target (including duplicates — if target has two 'a's, the window needs two as well). Hint: this is a variable-size window guided by a "how many required characters are currently satisfied" counter, not just a boolean set. For s = "ADOBECODEBANC" and target = "ABC", the expected output length is 4 (the substring "BANC").

Summary

  • Sliding window scans contiguous subarrays/substrings in O(n) by updating a running aggregate incrementally instead of recomputing it from scratch at every position.
  • Fixed-size windows keep a constant width and move both pointers together; variable-size windows grow with right and shrink with a while loop on left whenever a condition demands it.
  • Time complexity is O(n) for both flavors because left and right each move forward at most n times total across the whole run; space is O(1) for a simple running sum or up to O(k) when tracking a set/dict of window contents.
  • The brute-force alternative — recomputing each window’s aggregate from a fresh slice — costs O(n × k) or O(n²) and defeats the purpose of the pattern.
  • Common bugs: off-by-one window length (right - left + 1, not right - left) and shrinking with if instead of while when more than one shrink step may be needed per outer iteration.
  • Recognize the pattern from phrasing like "longest/shortest/maximum/minimum contiguous subarray or substring that satisfies…".