Sliding Window

Sliding window is what two pointers turns into when the "window" itself — not just its edges — is the thing carrying state: a running sum, a count per character, a max. The whole point is the same as two pointers: never redo work you've already paid for. Here that means never recomputing a window's sum/count/max from scratch when you slide it by one.

Two window shapes, and how to tell them apart

• Fixed size. The window's length is given up front (Average of Subarrays of Size K, Sliding Window Maximum). Sliding it by one always removes exactly one element (the one falling off the left) and adds exactly one (the one entering on the right). The update is O(1) per step regardless of how big the window is.
• Variable size, grow/shrink. The window's length isn't known in advance — it grows until some condition is violated (or satisfied), then shrinks from the left until it's valid again (Longest Substring Without Repeating Characters, Minimum Window Substring). The right pointer only ever moves forward; the left pointer only ever moves forward. Neither ever resets — that's what keeps the total work O(n) instead of O(n²), even though it looks like a loop inside a loop.

Why the naive approach is the trap here

Almost every sliding-window problem has an obvious brute force: try every window (or every substring), check it, keep the best. That's O(n²) at best, sometimes O(n·k) or O(n³) if checking a window itself isn't O(1). The entire skill is recognizing that a window's answer relates to the previous window's answer by only a small, cheap update — so you maintain state incrementally instead of rebuilding it.

// WRONG instinct: recompute the window's sum from scratch every slide -- O(n*k) total.
for (int i = 0; i + k <= n; ++i) {
    int sum = 0;
    for (int j = i; j < i + k; ++j) sum += nums[j];   // re-adds k elements every single time
    best = std::max(best, sum);
}

// RIGHT instinct: the window changed by exactly one element on each side -- O(n) total.
int sum = 0;
for (int i = 0; i < k; ++i) sum += nums[i];         // pay for the first window once
best = sum;
for (int i = k; i < n; ++i) {
    sum += nums[i] - nums[i - k];                      // add what entered, remove what left -- O(1)
    best = std::max(best, sum);
}

Common mistakes

• Recomputing a count/sum from scratch on every shrink step instead of decrementing incrementally — turns an O(n) solution back into O(n²) while still "looking like" sliding window.
• Forgetting to remove a map entry once its count hits zero (Fruit Into Baskets, Longest Substring with K Distinct) — a stale zero-count entry still counts toward "how many distinct keys are in the window," silently breaking the distinct-count check.
• Shrinking with the wrong condition — "shrink while a condition holds" (looking for the shortest valid window, like Minimum Window Substring) is a different loop than "shrink until a condition is restored" (looking for the longest valid window, like Longest Substring Without Repeating Characters). Copy-pasting the wrong shape silently returns the wrong extreme.
• Decreasing a "best seen so far" tracker when it shouldn't be decreased — Longest Repeating Character Replacement's max_freq is deliberately never decremented on shrink, because a stale-but-too-high value can only ever make the window shrink more conservatively, never accept a wrong answer. Removing that reasoning and "fixing" it to always stay accurate actually makes the sliding window logic more complex for no benefit.
• Using a hash map where a fixed-size array would do (26 lowercase letters, 256 ASCII values) — correct either way, but the array avoids hashing overhead and is the more "efficient developer" instinct once you know the input's character set is bounded.

The deque trick (Sliding Window Maximum)

Fixed-size windows are usually the easy case — until the thing you need from the window is its max, not its sum. A max can't be updated by just "add the incoming value" the way a sum can, because the max might be the element that's about to fall off the left edge. The fix: maintain a deque of indices, kept in strictly decreasing order of value. Any index whose value is ≤ the incoming value can never be the max again (the new value is both bigger and will outlive it) — so pop it immediately. This keeps every index pushed and popped at most once across the whole run, which is what makes it O(n) instead of O(n log n) (a heap) or O(n·k) (recompute per window).