Introduction to Sliding Window Pattern

Introduction to the Sliding Window Pattern

The sliding window pattern turns a naive nested-loop scan over a contiguous run of array or string elements into a single pass. Instead of recomputing an aggregate (sum, max, count of distinct characters, etc.) from scratch for every candidate window, you maintain the aggregate incrementally as a window's boundaries move: extend the window by including one new element on the right, and, when the window needs to shrink, retract it by excluding one element on the left. Both operations touch each array element a bounded number of times, which is what collapses the complexity from quadratic to linear.

This page covers two shapes of the pattern (fixed-size and variable-size windows), derives the complexity of each, and, critically, tells you when sliding window is the wrong tool, because two other named techniques — prefix sums and a monotonic deque — solve overlapping problems better under specific conditions.

Recognize the pattern

Reach for sliding window when a problem asks for something about every contiguous subarray or substring of an array or string, and the tracked quantity can be updated incrementally as the window moves by one position. Typical tells:

• "Find the maximum or average sum of any subarray of size K" (fixed-size window).
• "Find the smallest subarray whose sum is at least S" (variable-size window).
• "Find the longest substring with at most K distinct characters" (variable-size window).
• The words contiguous, substring, or subarray appear, as opposed to subsequence, which permits skipping elements. A subsequence has no two adjacent boundaries you can slide, so it generally needs dynamic programming instead.

Sliding window is one of several named techniques competing for this same problem space. The next section places it explicitly against the two closest alternatives so you know when to reach for something else.

When to use it, and when not to

Alternative 1: prefix-sum array

For the exact example used on this page — the sum of every window of size K in a fixed array — a prefix-sum array is the natural competing technique. Precompute prefix[i] = arr[0] + ... + arr[i-1] once in O(N) time and O(N) space; then the sum of any window [l, r] is prefix[r+1] - prefix[l] in O(1), for any l and r, not just ones reachable by sliding one step at a time.

• Use prefix sums instead when you need sums of arbitrary, non-adjacent ranges queried repeatedly (e.g. "answer Q range-sum queries after this array is built"), or when windows are not visited in left-to-right sliding order.
• Use sliding window instead when you only ever need windows visited in order with boundaries moving monotonically, and you want O(1) extra space rather than an O(N) auxiliary array — the running-sum technique below achieves the same O(N) total time as prefix sums without materializing the prefix array.

Alternative 2: monotonic deque

Sliding window's incremental-update trick works cleanly for aggregates that are cheaply reversible under removal — sum, count, XOR. It breaks down for max or min: when the element leaving the window on the left was the window's maximum, you cannot recover the new maximum from the old one in O(1); naively you'd rescan the window, which is back to O(N*K).

• Use a monotonic deque instead for "maximum/minimum of every window of size K." The deque stores indices in decreasing (or increasing) order of value, evicting from the back any index whose value is dominated by the newly-added element, and evicting from the front any index that has fallen outside the window. This keeps the window's max/min accessible in O(1) with amortized O(1) work per step, still O(N) overall.
• Use plain sliding window instead when the aggregate is sum/count/product (no undominated-element problem), where a simple running variable suffices and a deque is unneeded machinery.

When NOT to use sliding window at all

The variable-size "shrink while the condition holds" version of sliding window (e.g. "smallest subarray with sum at least S") relies on a monotonicity assumption: growing the window can only move the aggregate in one direction, and shrinking it can only move it back. This holds for sums only when all elements are non-negative. The moment the array can contain a negative number, growing the window can decrease the sum, so the two-pointer shrink logic silently gives wrong answers — it stops shrinking at points that no longer bound a valid answer, and can skip over the true minimal window entirely, with no exception or crash to signal the bug.

The worked example on this page — [2, 1, 5, 1, 3, -1, 4, 2] — contains a -1. That's fine for the fixed-size window sum in the first worked example below (fixed windows don't rely on monotonicity; every window is exactly K elements regardless of sign). But it means this same array is not safe input for the variable-size "shrink on threshold" technique later on this page without switching to a different approach (prefix sums plus binary search, or a deque-based technique) once negatives are possible. The variable-size example below is deliberately run on a non-negative array to keep the pattern valid, and that restriction is called out again at that point.

Fixed-size window: brute force vs. incremental — and the trade-off that matters more

Problem: given arr = [2, 1, 5, 1, 3, -1, 4, 2] and K = 5, find the maximum sum of any contiguous subarray of size K.

Brute force

For each of the N - K + 1 starting positions, sum K elements from scratch: (N - K + 1) * K additions in the worst case, which is O(N*K) time and O(1) extra space (or O(N) if you store every window's sum, not just the max).

Optimized: running sum

Compute the sum of the first window once (O(K) work, done exactly one time). Then slide: to move from window [i, i+K-1] to [i+1, i+K], add arr[i+K] and subtract arr[i] — two operations, regardless of K. Track a running max as you go.

Complexity derivation: the first window costs O(K). Each of the remaining N - K slides costs O(1). Total work is O(K) + O(N - K) * O(1) = O(K) + O(N - K) = O(N). Extra space is O(1): one running-sum variable and one running-max variable, no auxiliary array (O(N) only if every window's sum must be retained, e.g. to return the full list rather than just the max).

This before/after comparison (O(N*K) brute force vs. O(N) running sum) is a within-technique optimization — both versions are sliding window, one just recomputes and the other reuses. It is not a trade-off against a different named algorithm. The real cross-technique trade-offs are against prefix sums and the monotonic deque, covered above: pick sliding window over those when you have a simple reversible aggregate (sum/count) visited in strictly left-to-right window order and you want O(1) extra space; pick prefix sums when you need random-access range queries; pick a monotonic deque when the aggregate is max/min.

Traced worked example: fixed-size window (K = 5)

arr = [2, 1, 5, 1, 3, -1, 4, 2], N = 8, K = 5, so there are N - K + 1 = 4 windows.

Answer: maximum sum of any size-5 window is 12 (achieved by both window 1 and window 3). Total work: one O(K) initial sum plus three O(1) slides — O(N) overall, matching the derivation above, and no auxiliary array was needed beyond two scalars, so extra space is O(1).

Variable-size window: smallest subarray with sum at least S

This is the harder, more common interview shape flagged in "Recognize the pattern" above, and it works differently from the fixed-size case: the right pointer always advances, but the left pointer only advances (shrinks the window) while a condition continues to hold, rather than in lockstep with the right pointer.

Precondition: as established above, this technique requires all elements to be non-negative, so that growing the window never decreases the sum and shrinking it never increases the sum. Problem: given arr = [2, 1, 5, 1, 3, 2, 4, 2] (the earlier example's -1 replaced with a non-negative 2 specifically so this technique is valid) and S = 8, find the length of the smallest contiguous subarray with sum ≥ S.

Algorithm

1. Maintain left = 0, sum = 0, best = infinity.
2. For each right from 0 to N-1: add arr[right] to sum.
3. While sum >= S: record best = min(best, right - left + 1), then subtract arr[left] from sum and increment left (shrink as far as the condition allows).
4. Return best (or 0/none if it never dropped below infinity).

Traced example (S = 8)

Answer: smallest subarray with sum ≥ 8 has length 3 (the first window achieving length 3 was indices [0,2] = 2,1,5, sum 8). Complexity: the right pointer advances N times total; the left pointer also advances at most N times total across the whole run (it never resets backward), so total pointer movement is O(N), not O(N) per right-step — giving O(N) time overall, O(1) extra space.

Implementations

Fixed-size window (max sum of size-K subarray) — Java

public static int maxSumFixedWindow(int[] arr, int k) {
    int n = arr.length;
    if (n < k) throw new IllegalArgumentException("array shorter than window");
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int best = windowSum;
    for (int right = k; right < n; right++) {
        windowSum += arr[right] - arr[right - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

Fixed-size window — Go

func maxSumFixedWindow(arr []int, k int) int {
    n := len(arr)
    if n < k {
        panic("array shorter than window")
    }
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += arr[i]
    }
    best := windowSum
    for right := k; right < n; right++ {
        windowSum += arr[right] - arr[right-k]
        if windowSum > best {
            best = windowSum
        }
    }
    return best
}

Variable-size window (smallest subarray with sum ≥ S, non-negative elements only) — Java

public static int smallestSubarrayAtLeastS(int[] arr, int s) {
    int left = 0, sum = 0, best = Integer.MAX_VALUE;
    for (int right = 0; right < arr.length; right++) {
        sum += arr[right];
        while (sum >= s) {
            best = Math.min(best, right - left + 1);
            sum -= arr[left];
            left++;
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

Variable-size window — Go

func smallestSubarrayAtLeastS(arr []int, s int) int {
    left, sum, best := 0, 0, -1
    for right := 0; right < len(arr); right++ {
        sum += arr[right]
        for sum >= s {
            length := right - left + 1
            if best == -1 || length < best {
                best = length
            }
            sum -= arr[left]
            left++
        }
    }
    if best == -1 {
        return 0
    }
    return best
}

Sources

Compiled from: CLRS-style asymptotic analysis conventions for amortized two-pointer arguments; the classic "maximum sum subarray of size K" and "minimum size subarray sum" problem formulations as commonly presented in interview-preparation references (e.g. LeetCode #209 Minimum Size Subarray Sum); and the standard monotonic-deque construction for sliding-window maximum (LeetCode #239 Sliding Window Maximum) used here for the deque trade-off discussion.

Play with it

Step through the sliding window yourself — press Play and predict each fork: