Why We Need Sliding Window & How to Think About It
Imagine sitting on a train and looking at the landscape through a window. At any given moment, the view inside your window overlaps 90% with what you saw a split-second ago. Instead of repainting the entire view from scratch every time the train moves, you only need to process the new landscape sliver entering on the right and discard the old landscape sliver exiting on the left.
This is a Sliding Window. It is the ultimate optimization for contiguous subarray or substring problems. Instead of running a nested loop to recompute values from scratch for every possible range (which costs $O(n^2)$ or $O(n \cdot k)$), you maintain a single moving range. As the window boundaries slide, you update the state in $O(1)$ by adding the entering element and removing the leaving element, reducing the total time to $O(n)$.
Two Flavors
- Fixed-size window: The window width is constant (
k). Slide one step at a time, adding the newcomer and evicting the oldest element. - Variable-size window: Grow the
rightboundary greedily to look for solutions, and shrink theleftboundary only when a constraint is violated.
# Variable window: longest substring with at most K distinct characters
# Python
from collections import defaultdict
def longest_k_distinct(s: str, k: int) -> int:
count = defaultdict(int)
left = best = 0
for right, ch in enumerate(s):
count[ch] += 1
while len(count) > k: # constraint violated → shrink
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
best = max(best, right - left + 1)
return best
// Java
import java.util.HashMap;
import java.util.Map;
public int longestKDistinct(String s, int k) {
Map<Character, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char rightChar = s.charAt(right);
count.put(rightChar, count.getOrDefault(rightChar, 0) + 1);
while (count.size() > k) { // constraint violated → shrink
char leftChar = s.charAt(left);
count.put(leftChar, count.get(leftChar) - 1);
if (count.get(leftChar) == 0) {
count.remove(leftChar);
}
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
// C++
#include <string>
#include <unordered_map>
#include <algorithm>
int longestKDistinct(std::string s, int k) {
std::unordered_map<char, int> count;
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
count[s[right]]++;
while (count.size() > k) { // constraint violated → shrink
char leftChar = s[left];
count[leftChar]--;
if (count[leftChar] == 0) {
count.erase(leftChar);
}
left++;
}
best = std::max(best, right - left + 1);
}
return best;
}
State the loop invariant out loud in the interview: "the window [left, right]
is always valid after the inner while-loop." Each index enters once and leaves
once, so the two pointers move a total of 2n steps → O(n) even with the
nested loop.
Watch it run
The "add one, drop one" trick in motion — the window never recomputes its
sum from scratch. Change k and watch the work per slide stay O(1).
1/10Build the first window of size 3 by adding its elements once: sum = 15.
Complexity
| Brute force | Sliding window | |
|---|---|---|
| Time | O(n·k) / O(n²) | O(n) |
| Space | O(1) | O(k) for the window's bookkeeping |
Because the window only ever holds ≤ K+1 distinct keys — not the whole input — a sliding window is already a bounded-memory, one-pass algorithm, so it streams as-is. When the follow-up pushes further ("count distinct items, or the top-K, over an unbounded stream"), exact state stops fitting and you reach for streaming algorithms & sketches.
Think it through
The at-most-K code above is the template; now derive the most-asked variable window from scratch, with its own shrink rule. Think before each reveal.
PROBLEMReturn the LENGTH of the longest substring of s that has all distinct characters. s = 'abcabcbb' → 3 ('abc'). s = 'bbbbb' → 1.
- 1
Restate & edges
“What am I maximizing, and what are the trivial inputs?”
- 2
Brute force first
“Dumbest correct solution and its cost?”
unlocks after the stage above - 3
Find the pattern
“Grow the right edge by one. When does the window become invalid, and how do I fix it minimally?”
unlocks after the stage above - 4
Code the template
“Why is shrinking with a while-loop (not an if) correct, and still O(n)?”
unlocks after the stage above - 5
Cost & edge check
“Cost, and why is 'shrink instead of restart' provably valid here?”
unlocks after the stage above
// Java — Longest Substring Without Repeating Characters
import java.util.HashSet;
import java.util.Set;
public int longestUnique(String s) {
Set<Character> seen = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
while (seen.contains(ch)) { // duplicate → shrink from left
seen.remove(s.charAt(left));
left++;
}
seen.add(ch);
best = Math.max(best, right - left + 1);
}
return best;
}
// C++ — Longest Substring Without Repeating Characters
#include <string>
#include <unordered_set>
#include <algorithm>
int longestUnique(std::string s) {
std::unordered_set<char> seen;
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s[right];
while (seen.count(ch)) { // duplicate → shrink from left
seen.erase(s[left]);
left++;
}
seen.insert(ch);
best = std::max(best, right - left + 1);
}
return best;
}
Check yourself
1. Sliding window turns an O(n·k) or O(n²) brute force into O(n) because:
2. You shrink from the left instead of restarting the window because the constraint is monotonic. Here that means:
3. Longest subarray with sum exactly k, where the array contains NEGATIVE numbers — is a sliding window the right tool?
4. Fixed vs variable in 10 seconds: the problem hands you a window size k. It's:
Practice set
- Maximum sum subarray of size K — fixed window
- Longest substring without repeating characters — variable, shrink on dupe
- Minimum window substring — variable, need-map + formed counter
- Fruit into baskets — at most 2 distinct
- Permutation in string / find all anagrams — fixed window + frequency match
Practice — climb the ladder
The trigger: "longest/shortest/count of CONTIGUOUS subarray or substring satisfying X". Fixed size slides; variable size grows right, shrinks left.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up
fixed-size windows firstFixed window — add the entering element, subtract the leaving one; no recompute.
Window in disguise — running minimum behind you IS the left edge.
Core
variable windows with a validity conditionTHE variable window — grow right, shrink left until valid again; set tracks membership.
Validity = window size − max frequency ≤ k; subtler invariant, same skeleton.
- Permutation in StringMedium
Fixed window + frequency match — two counters kept in sync as it slides.
- Max Consecutive Ones IIIMedium
Budget-based validity (k zeros allowed) — spend entering, refund leaving.
- Fruit Into BasketsMedium
At most two distinct — the at-most-K family in its friendliest form.
Stretch
the boss fightsShrink to the SMALLEST valid window — need/have counters; the canonical hard window.
Monotonic deque carrying the max — windows + stacks-and-queues combined.