Pattern Reference
Sliding Window
"Turn O(n²) subarray loops into O(n) with a moving window."
Variations
One core pattern - multiple approaches. Each variation solves a different set of problems.
Deep Dive Tutorial
Every subarray problem at its core asks: "find a contiguous part of the array that satisfies some condition." The brute force is always two nested loops — O(n²). Sliding window is the observation that you don't need to recompute from scratch for each starting point. You can maintain a running state and slide a window across the array, adding from the right and removing from the left.
Fixed window — the size k is given upfront, window is always exactly k wide.
Dynamic window — the window grows and shrinks based on a condition (longest valid / shortest valid).
When to Reach for Sliding Window
| See This in the Problem | Think This |
|---|---|
| subarray / substring | Sliding window candidate |
| "longest ... with condition" | Dynamic window, expand until broken, shrink from left |
| "shortest ... with condition" | Dynamic window, shrink greedily once valid |
| "fixed length k" | Fixed window, slide one step at a time |
| "count of subarrays with exactly k" | atMost(k) − atMost(k−1) formula |
| input is ALL positive | Two pointer / dynamic window is safe |
| input has zeros | Use exact-count formula instead of direct window |
| input has negatives | Avoid sliding window, use prefix sum + hashmap |
The Core Templates
// Build first window, then slide
let sum = 0;
for (let i = 0; i < k; i++) sum += nums[i];
let maxSum = sum;
for (let i = k; i < n; i++) {
sum += nums[i]; // add incoming right element
sum -= nums[i - k]; // remove outgoing left element
maxSum = Math.max(maxSum, sum);
}let i = 0, j = 0, ans = 0;
while (j < n) {
// 1. Expand: add nums[j] to window state
state.add(nums[j]);
// 2. Shrink: while window is invalid, remove from left
while (!isValid(state)) {
state.remove(nums[i]);
i++;
}
// 3. Update answer with current valid window size
ans = Math.max(ans, j - i + 1);
j++;
}// When input has zeros, exact count can't be done by direct shrink.
// Use: count(exactly k) = count(at most k) − count(at most k−1)
const atMost = (goal) => {
if (goal < 0) return 0;
let i = j = ans = sum = 0;
while (j < n) {
sum += nums[j];
while (sum > goal) { sum -= nums[i]; i++; }
ans += j - i + 1; // all subarrays ending at j with sum ≤ goal
j++;
}
return ans;
};
return atMost(k) - atMost(k - 1);When the window [i..j] first becomes valid, ALL extensions to the right are also valid. Use
ans += n − j to count "this window + every longer window ending at or after j".DON'T use
ans += j − i + 1 in that scenario — that counts left-shrinking prefixes, a completely different set.Worked Problems
Input has 0s — can't direct-shrink to exact count. Use the formula.
Multi-source BFS — not sliding window, but same "enqueue all sources first" insight.
The One-Line Variation Trick
// Base: count subarrays with sum exactly k
const atMost = (goal) => {
let i = j = ans = sum = 0;
while (j < n) {
sum += nums[j]; // ← THIS LINE controls what we're tracking
while (sum > goal) { sum -= nums[i]; i++; }
ans += j - i + 1;
j++;
}
return ans;
};
return atMost(k) - atMost(k - 1);Count subarrays with exactly k ODD numbers
One-line Change:
Transform values to 0/1 parity, same formula applies
Longest substring with at most k distinct characters
One-line Change:
Change sum to distinct-character count, return max window not count
Count subarrays where max appears at least k times
One-line Change:
Once freq >= k, all right-extending windows are valid: ans += n - j
More Worked Problems
Even More Worked Problems
1. Can I define a window [lo, hi] with a valid/invalid state?
2. Is the state monotone — if [lo, hi] is invalid, is [lo, hi+1] also invalid? → shrink window
3. For COUNT problems: use atMost(k) - atMost(k-1) trick
4. Need max in window? → monotonic deque
5. Need sum/count in window? → simple two-pointer with running total
6. "At most k replacements/flips" → (windowSize - max_dominant_count) ≤ k
7. "Permutation in string" → fixed window + frequency matching (satisfied count)