Sliding Window Pattern

CodingJunior2 min read · 8 problemsUpdated Oct 28, 2026

Maintain a window of elements over a sequence; expand/shrink to satisfy a constraint while tracking an aggregate.

When to Use It

Contiguous subarray or substring problems: longest, shortest, max-sum, or constraint-bounded windows.

Classic example: Longest substring without repeating characters.

How It Works

The sliding window pattern tracks a contiguous range over a sequence using two indices, expanding by moving the right index and shrinking by moving the left. State within the window (sum, count, frequency map) is updated incrementally as elements enter and leave, this is what makes it O(n) instead of recomputing per window.

The shape of the window varies by problem. Fixed-size windows answer "best over all length-k substrings"; variable-size windows answer "longest/shortest satisfying constraint X". The shrink condition is the heart of the variant: shrink while the window violates the constraint, or shrink to the smallest valid window.

The win compared to nested loops is moving from O(n*k) or O(n^2) down to O(n) by reusing work across windows instead of recomputing. The pattern only works when the window's invariant can be updated in O(1) (or amortized O(1)) per pointer move, otherwise you're back to recomputation.

Key Insight

Each element enters and leaves the window at most once, so amortized work is O(n), the inner while loop doesn't make the algorithm O(n^2).

Sliding window: right expands, left shrinks while the window state stays valid.

Worked Example

Longest substring without repeating characters

s = "pwwkew"

right=0, "p": window "p", best 1
right=1, "w": window "pw", best 2
right=2, "w": "w" is already in the window, so left jumps from 0 to 2. Window "w"
right=3, "k": window "wk"
right=4, "e": window "wke", best 3
right=5, "w": "w" is already in the window, so left jumps from 2 to 3. Window "kew", still length 3

Result: 3 ("wke"). Each character entered the window once and left at most once, so six characters took six steps.

Templates

int left = 0;
int best = 0;
// initialize window state (counts, sum, etc.)

for (int right = 0; right < n; right++) {
    // expand: include arr[right] in window state

    while (/* window is invalid */) {
        // shrink: remove arr[left] from window state
        left++;
    }

    best = Math.max(best, right - left + 1);
}
return best;

left = 0
best = 0
# initialize window state (counts, sum, etc.)

for right in range(n):
    # expand: include arr[right] in window state

    while ...:  # window is invalid
        # shrink: remove arr[left] from window state
        left += 1

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

return best

Common Pitfalls

Forgetting to update window state when shrinking, e.g. decrementing a frequency map entry as left moves past it, or leaving stale zero-count keys in the map.
Using >= vs > in the shrink condition off by one, returning a window of length len-1 or len+1.
Tracking the window's running aggregate (sum/product) in a way that breaks for zero or negative values when the problem implicitly assumes positives.
Updating the answer at the wrong time: after shrinking when the problem wants the largest valid window, or before shrinking when it wants the smallest.
Confusing 'at most k' with 'exactly k' problems: 'exactly k' usually requires atMost(k) - atMost(k-1).

When It Breaks

The answer has to be contiguous. If it can skip elements (a subsequence), the window has nothing to slide over; that's usually dynamic programming.
Shrinking has to be safe: once a window breaks the constraint, every wider window with the same left edge must break it too. Negative numbers ruin that for sums, so "subarray sum equals k" with negatives needs prefix sums and a hash map.
The window's state has to update in O(1) as elements enter and leave. A max or min can't be subtracted back out, so pair the window with a monotonic deque.

Variations

Fixed-size window: no while loop, just slide right and subtract the element falling off the left.
Longest/shortest substring with constraint: variable window with a frequency map, shrink while invariant violated.
Sliding window maximum / median: pair the window with a monotonic deque or two heaps for O(log k) or amortized O(1) extrema.
Counting subarrays with property: use atMost(k) - atMost(k-1) to convert 'exactly' into two sliding-window passes.

Big O

Time: O(n)
Space: O(k)

Each element enters and exits the window at most once, so total work across both pointers is linear. Space is O(k) for whatever state the window tracks (frequency map of distinct chars, k-size deque, etc.).

Next PatternTwo Pointers