Maintain a subarray with two pointers. Shrink and grow to keep a constraint satisfied.

Sliding Window

What is sliding window?

The sliding window technique processes a contiguous subarray or substring by advancing two pointers - start and end - rather than recomputing the window from scratch each time. The window slides forward, and the cost of each slide is O(1) for the update, making the total O(n) instead of the O(n²) of a nested loop.

Two variants cover nearly all interview problems. The fixed-size window has a length given by the problem (always equal to k). You expand by adding the element at end, and when the window reaches size k, record the result then shrink by removing the element at start and advancing start. The variable-size window grows until a constraint is violated, then shrinks until the constraint is satisfied again.

The key invariant for variable windows: at all times, [start, end] satisfies the problem's constraint. When adding nums[end] breaks the constraint, move start forward until it is restored. Because start only ever moves forward and never backtracks, the total number of start advances across the entire algorithm is at most n - the nested shrink loop is O(n) amortized, not O(n²).

Different from two pointers in a subtle way: both techniques use two pointers moving in the same direction, but sliding window always centers on the concept of a maintained contiguous window. Two pointers often converge from opposite ends and the constraint is a relationship between two specific values rather than a window aggregate.

Core operations

Variant	Window size	When to expand	When to shrink	Returns
Fixed-size	Always k	Advance `end` each step	Advance `start` when `end - start >= k`	Running aggregate over each window
Variable-size (max)	Grows until invalid	Expand `end` each step	Shrink `start` until valid again	Longest valid window
Variable-size (min)	Shrinks once valid	Expand `end` each step	Shrink `start` while still valid	Shortest valid window

Key patterns

Fixed-size window

Keep a window of exactly k elements and slide it one step at a time, adding the element that enters and dropping the one that leaves.

The problem shape

Given an array and a window size k, compute a property (max, min, sum, average) of every k-element window. The result is the best such value (an integer or float), or the per-window output array. The brute-force version recomputes each window from scratch at O(n * k); sliding collapses that to O(n).

The key insight

Seed the aggregate once with the first k elements. Each step, add nums[end] and subtract nums[end - k] - the element exiting the back is always exactly k positions behind the one entering, so you never track a separate start. Each index is touched a constant number of times (one add when it enters, one subtract when it leaves), keeping the whole scan O(n) time and O(1) extra space beyond the aggregate.

Example: max sum of any window of size k. Given [1, 5, 0, 3, 2] and k = 2, the first window [1, 5] sums to 6 and nothing later beats it - the next three windows read 5, 3, and 5, so best never moves. Each slide is a single add and subtract: when end reaches index 2, add nums[2] = 0 and drop nums[0] = 1 for window_sum = 5. The walkthrough below traces exactly that input.

VisualizationMax sum of a fixed window

0/4

window_sum

best

Seed the first window nums[0:2] = 6. best starts there.

def max_sum_window(nums, k):▶    window_sum = sum(nums[:k])▶    best = window_sum    for end in range(k, len(nums)):        window_sum += nums[end] - nums[end - k]        best = max(best, window_sum)    return best

Note

Subtract nums[end - k] not nums[start] - for fixed windows, the leaving element is always k positions behind the entering element. Using end - k avoids tracking a separate start and removes a category of off-by-one bug.

Complexity: O(n) time, O(1) space (beyond the aggregate).

Solution walkthrough: Max sum of window k

Walk [1, 5, 0, 3, 2] with k = 2:

Seed window_sum = 1 + 5 = 6, best = 6 (window [0..1]).
end = 2: add nums[2] = 0, drop nums[0] = 1. window_sum = 5, best = 6.
end = 3: add nums[3] = 3, drop nums[1] = 5. window_sum = 3, best = 6.
end = 4: add nums[4] = 2, drop nums[2] = 0. window_sum = 5, best = 6.

Return best = 6. Each step is one add and one subtract - the window slides without ever rescanning.

Try it

def max_sum_fixed(nums: list[int], k: int) -> int:
    pass

Tests

assert max_sum_fixed([1, 5, 0, 3, 2], 2) == 6

assert max_sum_fixed([2, 10, -4, -7, 45, 6], 4) == 44

assert max_sum_fixed([5, 5, 5, 5], 2) == 10

assert max_sum_fixed([1, 2, 3, 4, 5], 5) == 15

assert max_sum_fixed([-1, -2, -3, -4], 2) == -3

Hints (3)

Variable-size window (expand/shrink)

Grow the window from the right until a constraint breaks, then shrink it from the left until the constraint holds again.

The problem shape

Given a string or array, find the longest (or shortest) contiguous subarray or substring satisfying a sum, count, or character constraint. The result is an integer length, or -1/0 as a sentinel for "no valid window". The brute-force version checks every start/end pair at O(n²); a window that only ever moves forward answers it in one O(n) pass.

The key insight

Invariant. [start, end] satisfies the constraint by the end of each outer step. Expand end by one each iteration; when adding nums[end] breaks the constraint, run an inner while loop that advances start until it holds again.
When to record the answer. Longest-window: record the length after the shrink (the window is valid then). Shortest-window: record inside the shrink loop while it is still valid.
Amortized O(n). The nested loop looks O(n²), but start never moves backward, so across the whole run it advances at most n times - every index enters the window once and leaves at most once.
Monotonicity is what makes it safe. Adding elements must push the window in one direction of validity (more invalid, or more valid). That one-way relationship is what makes the shrink direction unambiguous and lets start only move forward.

Example: longest substring without repeating characters. Given "xzyzxyzxx", end sweeps left to right while a character-count map tracks the window, and every duplicate shrinks it from the left: the second z (index 3) evicts the x and z at indices 0-1, and the third x (index 7) evicts the one at index 4. The longest valid window is "xzy" at indices 0-2, length 3. The visualization below walks the full expand-and-shrink trace.

VisualizationLongest Substring Without Repeating Characters

0/27

start

end

window

best

start

char_count

{ }

Empty window. char_count is empty, best is 0.

from collections import defaultdict def longest_without_repeating(s):▶    char_count = defaultdict(int)▶    start = 0▶    best = 0    for end in range(len(s)):        char_count[s[end]] += 1        while char_count[s[end]] > 1:  # window is invalid: duplicate present            char_count[s[start]] -= 1            start += 1        best = max(best, end - start + 1)    return best

Note

The inner while loop is O(n) total, not O(n) per iteration - start never moves backward, so across all outer loop steps it advances at most n times. The nested loop looks O(n²) but is O(n) amortized.

Complexity: O(n) time, O(alphabet size) space for the frequency map.

Solution walkthrough: Longest substring without repeating characters

Walk "xzyzxyzxx":

end=0..2 expand: window grows to "xzy", best = 3. No duplicates.
end=3 (z): count of z becomes 2 - invalid. Shrink: drop s[0]='x', start=1. Valid again, window "yz", best = 3.
end=4 (x): count of x becomes 2 - invalid. Shrink: drop s[1]='z', start=2. best = 3.
end=5 (y): count of y becomes 2 - invalid. Shrink: drop s[2]='y', start=3. Window is "zx", best = 3.
end=6 (z): count of z becomes 2 - invalid. Shrink: drop s[3]='z' then s[4]='x', start=5. Window "yz", best = 3.
end=7 (x): count of x becomes 2 - invalid. Shrink: drop s[5]='y' then s[6]='x', start=7. Window "zx", best = 3.
end=8 (x): count of x becomes 2 - invalid. Shrink: drop s[7]='z' then s[8]='x', start=8. Window "x", best = 3.

Return best = 3. Every character enters the window once and leaves at most once.

Try it

from collections import defaultdict

def longest_without_repeating(s: str) -> int:
    pass

Tests

assert longest_without_repeating("xzyzxyzxx") == 3

assert longest_without_repeating("kkkkk") == 1

assert longest_without_repeating("qvffdq") == 3

assert longest_without_repeating("") == 0

assert longest_without_repeating("abcde") == 5

Hints (3)

When to reach for sliding window

The problem involves a contiguous subarray or substring with a sum, count, or character constraint.
The problem gives a window of size k and asks for a property of each window - fixed window.
The problem asks for the longest or shortest subarray satisfying a condition - variable window.
You see a nested loop that re-scans elements the outer loop already visited - sliding window eliminates the inner scan.
The problem mentions minimum window containing, permutation in string, or fruit into baskets - all variable sliding window.
The constraint is monotonic: adding more elements makes the window consistently more or less valid.