Sliding Window
Think of it like this
You're looking out of a moving train window. As the train moves, new scenery enters from the right and old scenery leaves from the left. At every moment you only care about what's in the window right now — not all the scenery from the beginning of the journey.
The sliding window pattern does exactly this for arrays and strings: maintain a running aggregate (sum, count, max) for a subarray, and update it by adding the new right element and removing the old left element — instead of recomputing from scratch.
arr = [2, 4, 7, 1, 9, 3, 6], window size k = 3
Naive O(n·k): [2,4,7]=13 [4,7,1]=12 [7,1,9]=17 [1,9,3]=13 [9,3,6]=18
Sliding O(n): start=2+4+7=13
step: 13 - 2(left) + 1(right) = 12
step: 12 - 4 + 9 = 17
step: 17 - 7 + 3 = 13
step: 13 - 1 + 6 = 18
Same answers. But each step is O(1) instead of O(k). Total: O(n).Two Types of Windows
| Type | Window size | Right pointer | Left pointer |
|---|---|---|---|
| Fixed | Always k | Moves right each step | Trails right by k |
| Variable | Grows/shrinks | Expand when valid | Shrink when constraint violated |
Fixed Window
Use when the problem asks about a specific subarray size.
// Maximum sum of any subarray of size k
function maxSumFixed(arr, k) {
if (arr.length < k) return null;
// Build initial window
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += arr[i];
let maxSum = windowSum;
// Slide: add right element, remove left element
for (let right = k; right < arr.length; right++) {
windowSum += arr[right] - arr[right - k]; // O(1) per step
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// First negative number in every window of size k
function firstNegativeInWindow(arr, k) {
const deque = []; // indices of negative numbers in window
const result = [];
for (let right = 0; right < arr.length; right++) {
if (arr[right] < 0) deque.push(right);
// Remove indices outside the window
if (deque.length && deque[0] < right - k + 1) deque.shift();
// Window is complete
if (right >= k - 1) result.push(deque.length ? arr[deque[0]] : 0);
}
return result;
}Variable Window (The Important One)
The window expands as long as it satisfies a constraint. When the constraint is violated, shrink from the left until it's valid again.
Template:
left = 0
for right in 0..n:
add arr[right] to window
while window VIOLATES constraint:
remove arr[left] from window
left++
// window is now valid — update answer
answer = best(answer, right - left + 1)Example: Longest substring with at most K distinct characters
s = "aabacbebebe", k = 3
Expand right:
"a" → 1 distinct ✓
"aa" → 1 ✓
"aab" → 2 ✓
"aaba" → 2 ✓
"aabac" → 3 ✓
"aabacb" → 3 ✓
"aabacbe" → 4 ✗ → SHRINK from left:
remove 'a' → "abacbe" → 4 ✗
remove 'a' → "bacbe" → 4 ✗
remove 'b' → "acbe" → 4 ✗
remove 'a' → "cbe" → 3 ✓ answer = max(6, 3) = 6 so far
Continue...function longestSubstringKDistinct(s, k) {
const freq = new Map();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
// Expand: add right char to window
freq.set(s[right], (freq.get(s[right]) ?? 0) + 1);
// Shrink: while more than k distinct chars, remove from left
while (freq.size > k) {
const leftChar = s[left++];
freq.set(leftChar, freq.get(leftChar) - 1);
if (freq.get(leftChar) === 0) freq.delete(leftChar);
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Example: Minimum window substring (contains all chars of pattern)
function minWindow(s, t) {
const need = new Map();
for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
let have = 0, required = need.size;
let left = 0, minLen = Infinity, minStart = 0;
const window = new Map();
for (let right = 0; right < s.length; right++) {
const ch = s[right];
window.set(ch, (window.get(ch) ?? 0) + 1);
// Did we satisfy a character's required count?
if (need.has(ch) && window.get(ch) === need.get(ch)) have++;
// Try to shrink while window is valid
while (have === required) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
const leftCh = s[left++];
window.set(leftCh, window.get(leftCh) - 1);
if (need.has(leftCh) && window.get(leftCh) < need.get(leftCh)) have--;
}
}
return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen);
}Sliding Window (Max Sum Subarray k=3)
1 / 3
2
[0]
1
[1]
↑ Window
5
[2]
1
[3]
3
[4]
2
[5]
Initial window of size 3. Sum = 2+1+5 = 8.
Recognizing Sliding Window Problems
Look for these phrases in problem statements:
| Phrase | Type |
|---|---|
| "subarray/substring of size k" | Fixed window |
| "longest subarray/substring with [constraint]" | Variable window (maximize length) |
| "shortest subarray/substring that [condition]" | Variable window (minimize length) |
| "maximum/minimum in every window of size k" | Fixed window + monotonic deque |
| "at most k", "at least k", "exactly k" | Variable window with count tracking |
Monotonic Deque for Window Maximum
Standard sliding window can't give you the maximum of the current window in O(1). The monotonic deque fixes this: it stores indices in decreasing order of values, so the front is always the current window's max.
function slidingWindowMax(nums, k) {
const deque = []; // stores indices, decreasing by nums[index]
const result = [];
for (let right = 0; right < nums.length; right++) {
// Remove expired indices (outside window)
while (deque.length && deque[0] <= right - k) deque.shift();
// Remove useless smaller values from back
while (deque.length && nums[deque[deque.length - 1]] < nums[right]) deque.pop();
deque.push(right);
if (right >= k - 1) result.push(nums[deque[0]]); // front = max
}
return result;
}
// nums=[3,1,2,5,1], k=3
// Window [3,1,2]: deque=[0], result=[3]
// Window [1,2,5]: deque=[3], result=[3,5] (5 is max)
// Window [2,5,1]: deque=[3,4], result=[3,5,5]Real-World Frontend Application
- Moving average charts: A financial dashboard showing "30-day moving average" — slide a fixed window over daily prices, O(n) total
- Rate limiting: Track API calls in the last 60 seconds — variable window where calls outside 60s fall off the left end
- Text editor autocomplete: Find all substrings matching a partial query in O(n) using a sliding window over the document
- Video buffering strategy: Maintain a fixed window of pre-loaded video segments; load the next as the current plays
Complexity
| Window Type | Time | Space |
|---|---|---|
| Fixed window (sum/count) | O(n) | O(1) |
| Variable window (with HashMap) | O(n) | O(k) where k = distinct elements |
| Window maximum (monotonic deque) | O(n) | O(k) |
| vs naive nested loops | O(n·k) | O(1) |
Common Mistakes
| Mistake | What Happens | Fix |
|---|---|---|
| Shrinking before updating answer | Misses the valid window size | Update answer before or while shrinking |
| Forgetting to decrement count on shrink | Window thinks deleted chars are still present | freq[char]--; if freq[char] == 0: delete |
| Wrong shrink condition | Shrinks too much or too little | Re-read the constraint: violate = shrink, not "shrink when you can" |
| Not handling empty/single-element | Crash on edge case | Guard with early return |
Key Problems to Solve
| # | Problem | Type | Difficulty |
|---|---|---|---|
| 1 | Maximum Average Subarray I | Fixed window | Easy |
| 2 | Longest Substring Without Repeating Chars | Variable window | Medium |
| 3 | Longest Substring with At Most K Distinct | Variable window | Medium |
| 4 | Permutation in String | Fixed window + char count | Medium |
| 5 | Minimum Size Subarray Sum | Variable window | Medium |
| 6 | Fruit Into Baskets | Variable window (2 distinct) | Medium |
| 7 | Minimum Window Substring | Variable window + need/have | Hard |
| 8 | Sliding Window Maximum | Fixed window + monotonic deque | Hard |
| 9 | Longest Repeating Character Replacement | Variable window | Medium |
| 10 | Subarrays with K Different Integers | Exactly K = at-most-K minus at-most-(K-1) | Hard |