Sliding Window
Maintain a contiguous window and update it incrementally. Fixed-size windows, variable windows for longest/shortest, and the 'at most K' counting trick.
The idea
A window is a contiguous range [left, right]. Instead of recomputing something for every subarray (O(n²) or worse), slide the window and update the state incrementally as elements enter on the right and leave on the left. Both pointers only move forward, so it's O(n).
Try the sliding-window demo in the visualizers.
Type 1: Fixed-size window
The window size k is given. Add a[right], remove a[right − k].
def max_sum_k(a, k):
window = sum(a[:k])
best = window
for right in range(k, len(a)):
window += a[right] - a[right - k]
best = max(best, window)
return best
long long maxSumK(const vector<int>& a, int k) {
long long window = 0;
for (int i = 0; i < k; i++) window += a[i];
long long best = window;
for (int r = k; r < (int)a.size(); r++) {
window += a[r] - a[r - k];
best = max(best, window);
}
return best;
}
The state doesn't have to be a sum — it can be a character count array (anagram search), a set of distinct values, or a monotonic deque (window maximum).
def find_anagrams(s, p):
if len(p) > len(s):
return []
need, have = [0] * 26, [0] * 26
for ch in p:
need[ord(ch) - 97] += 1
res = []
for i, ch in enumerate(s):
have[ord(ch) - 97] += 1
if i >= len(p):
have[ord(s[i - len(p)]) - 97] -= 1
if have == need: # 26 comparisons: still O(26n)
res.append(i - len(p) + 1)
return res
Type 2: Variable window — longest valid
Expand right every step. While the window is invalid, shrink from the left. After fixing, the window is valid → update the answer.
def longest_valid(a):
left = 0
state = ... # counts, sums, etc.
best = 0
for right, x in enumerate(a):
add(state, x)
while not valid(state):
remove(state, a[left])
left += 1
best = max(best, right - left + 1)
return best
Example: longest substring without repeating characters
def length_of_longest_substring(s):
count = {}
left = best = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
while count[ch] > 1: # invalid: ch is duplicated
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
int lengthOfLongestSubstring(string s) {
int cnt[128] = {0}, left = 0, best = 0;
for (int right = 0; right < (int)s.size(); right++) {
cnt[s[right]]++;
while (cnt[s[right]] > 1) cnt[s[left++]]--;
best = max(best, right - left + 1);
}
return best;
}
Example: longest repeating character replacement
A window is valid if we can make it all one letter with ≤ k replacements: length − maxFreq ≤ k.
def character_replacement(s, k):
count = [0] * 26
left = max_freq = best = 0
for right, ch in enumerate(s):
count[ord(ch) - 65] += 1
max_freq = max(max_freq, count[ord(ch) - 65])
while (right - left + 1) - max_freq > k:
count[ord(s[left]) - 65] -= 1
left += 1
best = max(best, right - left + 1)
return best
Type 3: Variable window — shortest valid
Expand until the window becomes valid, then shrink while it stays valid, recording the answer inside the inner loop.
def min_subarray_len(target, nums):
left = total = 0
best = float("inf")
for right, x in enumerate(nums):
total += x
while total >= target: # valid: try to shrink
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float("inf") else best
Example: minimum window substring
Track how many distinct characters currently meet their required count (formed) so validity is O(1) to check.
from collections import Counter
def min_window(s, t):
need = Counter(t)
required = len(need)
have = {}
formed = left = 0
best = (float("inf"), 0, 0)
for right, ch in enumerate(s):
have[ch] = have.get(ch, 0) + 1
if ch in need and have[ch] == need[ch]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = (right - left + 1, left, right)
out = s[left]
have[out] -= 1
if out in need and have[out] < need[out]:
formed -= 1
left += 1
return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]
string minWindow(string s, string t) {
int need[128] = {0}, have[128] = {0}, required = 0;
for (char c : t) if (need[c]++ == 0) required++;
int formed = 0, left = 0, bestLen = INT_MAX, bestL = 0;
for (int right = 0; right < (int)s.size(); right++) {
char c = s[right];
if (++have[c] == need[c] && need[c] > 0) formed++;
while (formed == required) {
if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestL = left; }
char o = s[left++];
if (have[o]-- == need[o] && need[o] > 0) formed--;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}
Type 4: Counting subarrays
If a window [left, right] is valid and validity is preserved when shrinking, then every subarray ending at right and starting in [left, right] is valid: that's right − left + 1 subarrays.
def num_subarray_product_less_than_k(nums, k):
if k <= 1:
return 0
prod, left, count = 1, 0, 0
for right, x in enumerate(nums):
prod *= x
while prod >= k:
prod //= nums[left]
left += 1
count += right - left + 1
return count
The “exactly K = at most K − at most (K−1)” trick
“Exactly K distinct” isn't monotonic (shrinking can drop below K), but “at most K” is.
def at_most(nums, k):
count, left, res = {}, 0, 0
for right, x in enumerate(nums):
count[x] = count.get(x, 0) + 1
while len(count) > k:
count[nums[left]] -= 1
if count[nums[left]] == 0:
del count[nums[left]]
left += 1
res += right - left + 1
return res
def subarrays_with_k_distinct(nums, k):
return at_most(nums, k) - at_most(nums, k - 1)
Same trick: Binary Subarrays With Sum, Count Number of Nice Subarrays (exactly k odd numbers).
Choosing the window type
| Question asks for | Loop shape | Answer updated |
|---|---|---|
| max/min over windows of size k | fixed | after each slide |
| longest window satisfying X | shrink while invalid | after the while loop |
| shortest window satisfying X | shrink while valid | inside the while loop |
| number of subarrays satisfying X (monotone) | shrink while invalid | add right − left + 1 |
| number with exactly K | two “at most” calls | subtract |
Common mistakes
- Applying a sum-based window to arrays with negative numbers.
- Updating the answer in the wrong place (inside vs. after the shrink loop).
- Forgetting to delete zero-count keys when using
len(map)as “distinct count”. - Off-by-one in fixed windows: the element leaving is
a[right − k]. - Using
ifinstead ofwhilefor shrinking (one step may not restore validity).
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.