Sliding Window

6 questions, two of them Hard. This section contains the most templated patterns in the 150 — once you can tell the three window shapes apart, most of these write themselves.

The one idea

Keep a contiguous range [left, right] plus a summary of what's inside it, and when the range moves, UPDATE the summary instead of recomputing it.

That's the whole technique. The brute force's inner loop re-derives a property of the window from scratch; the window maintains it incrementally.

Seeing where the saving comes from

"Largest sum of any 3 consecutive elements in [1, 4, 2, 10, 2, 3, 1]":

window at i=0:  [1, 4, 2] 10  2  3  1     sum = 7
window at i=1:   1 [4, 2, 10] 2  3  1     sum = 16

They share 4 and 2. Re-adding them is wasted work — the only real change is that one element left and one entered. So sum = sum - leaving + entering, in O(1).

O(n · k) becomes O(n).

When it applies — all three must hold

1. The answer is a contiguous subarray or substring. Non-contiguous (a subsequence) means dynamic programming instead.
2. The summary updates in O(1) per step — a sum, a count array, a distinct-count. A median does not, which is why that variant needs different machinery.
3. Validity is monotonic in window size — growing can only make the window "more invalid". Without this, shrinking from the left is not safe, and windowing is simply the wrong tool.

Condition 3 is the one candidates skip. It's what licenses the shrink loop.

The three templates

Learn which one a question needs, and the code follows.

Fixed size k — add the entering element, drop the leaving one, record when full.

for (int right = 0; right < n; right++) {
    add(nums[right]);
    if (right >= k - 1) { record(); remove(nums[right - k + 1]); }
}

Longest valid — expand always; shrink while invalid; record after the loop.

for (int right = 0; right < n; right++) {
    add(nums[right]);
    while (isInvalid()) { remove(nums[left]); left++; }
    best = Math.max(best, right - left + 1);
}

Shortest valid — expand until valid; shrink while still valid; record inside the loop.

for (int right = 0; right < n; right++) {
    add(nums[right]);
    while (isValid()) { best = Math.min(best, right - left + 1); remove(nums[left]); left++; }
}

The difference between longest and shortest is one line's position: longest records outside the shrink loop (after validity is restored); shortest records inside it (while still valid).

Why it's O(n) despite the nested loop

left and right each only move forward, and neither exceeds n. So together they take at most 2n steps, no matter how the inner while is written. Some iterations shrink five times; then five later iterations shrink none. That's aggregate accounting — the same argument behind the monotonic stack and Longest Consecutive Sequence.

Two pointers vs. sliding window

Settled once, since Section 2 introduced the other one:

How to work this section

1. Read §1 and §2 only, then attempt cold with a timer — 20 min Easy, 35 Medium, 45 Hard.
2. After the attempt, read §3 and §4 and diff against your reasoning.
3. Use the counter-questions in §3 as a quiz — for each approach, cover the answers and try to defend it yourself.
4. Read §7 last: the modified-constraint variants.

What to carry forward

• Which template a question needs, identified from its phrasing alone.
• The habit of writing the window length as right - left + 1 and checking it on a two-element example.
• Deriving a validity condition rather than recalling it — Q3's windowLength − maxFreq <= k is the canonical example.
• The monotonic deque (Q6), which is the same idea as the monotonic stack with eviction from both ends.