Sliding window is a problem-solving pattern where you use two pointers to define a "window" and slide them over a data structure, typically an array or a string, to find subarrays or substrings that meet a certain requirement.

This approach can reduce the time complexity of many array and string problems from O(n²) to O(n).

In this chapter, I'll break down:

A sliding window is a technique that maintains a subset of elements from an array or string, moving through the data one position at a time. As the window slides, we update our result incrementally rather than recomputing from scratch.

The window is defined by two pointers:

Updates happen incrementally. When sliding from one position to the next:

The window in a Sliding Window algorithm expands, shrinks, and slides over a data structure:

Sliding window relies on a simple observation: consecutive windows overlap significantly. If we have already computed something for window [i, i+k-1], the next window [i+1, i+k] shares k-1 elements with the previous one. We only need to account for one element leaving and one element entering, instead of recomputing everything.

Consider finding the sum of every k consecutive elements:

Brute Force Approach:

Sliding Window Approach:

Reusing computation in this way reduces O(n*k) to O(n). Across the full iteration, each element enters the window at most once and leaves at most once. The total work is O(n), amortized, since the inner while doesn't run on every outer iteration.

The variable-size template has a for loop with a while loop nested inside it. At first glance this looks like O(n²), but it's actually O(n). Here's why.

The outer for loop advances right from 0 to n - 1. That's exactly n iterations.

The inner while loop advances left. Across the entire execution of the algorithm, left also moves from 0 to at most n - 1. That's at most n iterations TOTAL across all outer iterations combined, not n iterations per outer iteration.

Total work: n outer iterations + at most n inner iterations = O(n).

The cost of the inner loop is amortized across all outer iterations. On some outer iterations the while loop runs many times, on others it doesn't run at all, but the total inner-loop work is bounded by left advancing through the array once. A common mistake when analyzing sliding window is to multiply the outer and inner loop bounds and conclude O(n²). The correct way is to count how many times each pointer moves over the entire run.

Sliding window problems fall into two categories based on how the window size behaves.

Fixed-size window problems follow a predictable pattern. We first build the initial window of size k, then slide it through the array by removing the leftmost element and adding the next element on the right.

In variable-size window problems, the window grows and shrinks based on a condition. We use two pointers, left and right, where right expands the window and left contracts it.

The general pattern is: expand until a condition is violated, then shrink until the condition is restored.

There are two variations depending on what we are optimizing.

Finding Maximum Length:

Finding Minimum Length:

Some sliding window problems ask you to count subarrays where some property holds exactly K times. Examples include "Subarrays with K Different Integers" (LeetCode 992), "Count Number of Nice Subarrays" (LeetCode 1248), and "Binary Subarrays with Sum" (LeetCode 930).

A direct sliding window for "exactly K" is awkward. When the window has the property exactly K times and we extend it, the count might jump to K+1, or it might stay at K. When we try to shrink, we don't have a clean rule for when to stop, since both "K" and "K-1" are reachable from a K window. The "exactly K" predicate isn't monotone with respect to window size, so the standard expand-and-shrink template breaks down.

The fix is to reframe the problem.

Define atMost(K) as the number of subarrays where the property holds at most K times. This IS solvable with sliding window, since the "at most K" predicate is monotone: shrinking a window can only decrease the count, never increase it. Once the count drops to K or below, it stays there as we shrink further.

Then the answer is:

To see why, think about what each subarray contributes. Every subarray has some actual property count j. That subarray is counted in atMost(K) if and only if j <= K. So atMost(K) counts subarrays with property count 0, 1, 2, ..., K, and atMost(K-1) counts subarrays with property count 0, 1, ..., K-1. The difference is subarrays with property count equal to exactly K.

Here's the template applied to "Subarrays with K Different Integers":

The line result += right - left + 1 is the counting step. After the while loop runs, every subarray ending at right and starting anywhere from left to right is valid, since the window [left, right] has at most k distinct elements, and any suffix of it also has at most k. The number of such subarrays is right - left + 1. Summing this across all right values counts every valid subarray exactly once, because each subarray has a unique right endpoint.

Reach for sliding window when you see these patterns:

1. Contiguous subarray or substring

The problem asks about elements that are next to each other. Sliding window works on contiguous sequences, not subsequences.

2. Some form of "longest," "shortest," "maximum," or "minimum"

We are optimizing some property of a contiguous segment.

3. The "expand and shrink" mental model applies

A variable-size sliding window expands until a condition breaks, then shrinks until the condition is satisfied again.

4. O(n) solution seems possible

If brute force is O(n^2) or O(n*k) and you suspect O(n) is achievable, sliding window is often the solution.

When NOT to use sliding window:

Sliding window works only when the window-validity predicate is monotone, that is, shrinking the window can only move from "invalid" to "valid" (or vice versa), not flip back and forth. This is why sum-target problems with negative numbers can't use sliding window directly: removing an element doesn't reliably decrease the sum.

The pointer-advancing logic in sliding window problems is almost always the same. What changes from problem to problem is what we track inside the window and how we update it when elements enter or leave.

The choice of state structure is what determines how hard a sliding window problem is. Pick the wrong structure and the add/remove operations become O(n), turning the whole algorithm into O(n²).

Sliding Window Maximum (LeetCode 239) is worth calling out as a distinct variant. The window is fixed size, but the goal is to report the maximum of every window. A naive approach scans the window each time, giving O(n*k). The efficient solution maintains a monotonic deque of indices such that the values at those indices are strictly decreasing. The front of the deque is always the index of the maximum in the current window. Each element is added to the deque once and removed at most once, so the total work is O(n) despite the fact that the inner deque operations look like they could blow up.