Published
Sliding Window Technique: Patterns, Templates and 8 Solved Problems
When to use a sliding window, the three templates that cover almost every problem, and eight worked LeetCode solutions with tested Python code.
The sliding window technique turns many “check every subarray” problems from O(n²) or worse into a single O(n) pass. You keep a range [left, right] over the array or string, update a small summary of what’s inside it as the edges move, and never go back. This guide covers when to use it, the three templates you need, eight worked LeetCode problems with tested Python code, and how it differs from two pointers and prefix sums.
What is the sliding window technique?
A window is a contiguous part of the input: nums[left..right] or s[left..right]. Instead of recomputing an answer for every possible window from scratch, you:
- Extend the window by moving
rightone step and adding the new element to your summary (a running sum, a character count, the last index of each character…). - Shrink it by moving
leftforward, removing elements from the summary, whenever the window breaks the rule (or, for “shortest” problems, while it still satisfies the rule). - Record the answer from the current window.
Both left and right only move forward, so each element enters the window once and leaves at most once. That’s why the whole pass is O(n), even though the code has a while loop inside a for loop.
When to use it: the signals
Reach for a sliding window when a problem has most of these:
- The answer is about a contiguous subarray or substring (not a subsequence).
- It asks for the longest, shortest, maximum/minimum sum, number of windows, or “does any window…” under a condition.
- The condition can be checked from a summary you can update incrementally: a sum, counts of characters, number of distinct values, the max inside the window.
- Validity is monotonic: if a window is invalid, every larger window containing it is also invalid (or the reverse for “shortest” problems).
If the problem says subsequence, or the numbers can be negative and you need an exact sum, the window idea usually breaks. See sliding window vs prefix sums below.
Fixed vs variable windows
| Fixed-size window | Variable-size window | |
|---|---|---|
| Window length | Always k | Grows and shrinks |
| Typical question | ”Max sum / average of any k consecutive elements”, “all anagrams of p in s" | "Longest substring with…”, “shortest subarray with sum ≥ target” |
Move left when | The window exceeds k | The window becomes invalid (longest) or while it stays valid (shortest) |
| Extra structure | Running sum or counts; a deque for window max/min | Counts, last-seen indices, number of distinct items |
The three templates
Template 1: fixed size k
window = sum(nums[:k]) # summary of the first window
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add the entering element, drop the leaving one
best = max(best, window)
Template 2: variable size, longest valid window
left = 0
for right, x in enumerate(items):
add(x) # 1. extend
while window_is_invalid(): # 2. shrink until valid again
remove(items[left])
left += 1
best = max(best, right - left + 1) # 3. the window is valid here
Template 3: variable size, shortest valid window
left = 0
for right, x in enumerate(items):
add(x)
while window_is_valid(): # shrink while it stays valid, recording each time
best = min(best, right - left + 1)
remove(items[left])
left += 1
The only difference between templates 2 and 3 is where you record the answer: after shrinking (longest) or inside the shrink loop (shortest).
The same templates in Java
import java.util.HashMap;
import java.util.Map;
public class SlidingWindow {
// Variable-size window template: longest substring with at most k distinct characters.
static int longestAtMostKDistinct(String s, int k) {
Map<Character, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
count.merge(s.charAt(right), 1, Integer::sum); // 1. add the new element
while (count.size() > k) { // 2. shrink while invalid
char out = s.charAt(left++);
if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);
}
best = Math.max(best, right - left + 1); // 3. window is valid: record
}
return best;
}
// Fixed-size window template: maximum sum of any k consecutive elements.
static long maxSumOfK(int[] nums, int k) {
long window = 0;
for (int i = 0; i < k; i++) window += nums[i];
long best = window;
for (int i = k; i < nums.length; i++) {
window += nums[i] - nums[i - k]; // add the entering, drop the leaving
best = Math.max(best, window);
}
return best;
}
public static void main(String[] args) {
System.out.println(longestAtMostKDistinct("eceba", 2)); // 3 ("ece")
System.out.println(maxSumOfK(new int[]{2, 1, 5, 1, 3, 2}, 3)); // 9 (5+1+3)
}
}
Output:
3
9
Why it’s O(n)
Count the moves, not the loops. right moves n times. left also only moves forward and can never pass right, so across the whole run it moves at most n times. Every add and remove is O(1) with a hash map or array of counts, so the total is O(n) time. Space is O(k) or O(alphabet size) for the summary.
Eight worked problems
All eight solutions below come from one file that also checks each function against a brute force on 300 random inputs. Running that file prints:
12.75
3 3
4
2
[0, 6]
'BANC'
[3, 3, 5, 5, 6, 7]
7
300 random cases per problem match brute force
1. Maximum Average Subarray I (LeetCode 643): fixed window
Find the maximum average of any k consecutive numbers. This is template 1 directly; divide by k at the end.
# 643. Maximum Average Subarray I (fixed window)
def find_max_average(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best / k
find_max_average([1, 12, -5, -6, 50, 3], 4) returns 12.75 (the window [12, -5, -6, 50]).
2. Longest Substring Without Repeating Characters (LeetCode 3): longest
The window is valid when no character repeats. Instead of shrinking one step at a time, remember each character’s last index and jump left just past the previous copy. The >= left check ignores copies that are already outside the window.
# 3. Longest Substring Without Repeating Characters (variable, longest)
def length_of_longest_substring(s):
last, left, best = {}, 0, 0
for right, ch in enumerate(s):
if last.get(ch, -1) >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return best
"abcabcbb" → 3 ("abc"), "pwwkew" → 3 ("wke").
3. Longest Repeating Character Replacement (LeetCode 424): longest
You may change up to k characters. A window can be made uniform if length - (count of its most frequent character) ≤ k. Track counts and the highest count seen.
# 424. Longest Repeating Character Replacement (variable, longest)
def character_replacement(s, k):
count, left, top, best = defaultdict(int), 0, 0, 0
for right, ch in enumerate(s):
count[ch] += 1
top = max(top, count[ch])
while (right - left + 1) - top > k: # more than k cells need changing
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
top is never decreased when the window shrinks. That’s safe: the answer can only improve when a window with a higher top count appears, so a stale top never produces a wrong larger answer. "AABABBA" with k = 1 gives 4.
4. Minimum Size Subarray Sum (LeetCode 209): shortest
Shortest subarray with sum ≥ target, all numbers positive. Template 3: once the sum reaches the target, record and shrink while it stays valid.
# 209. Minimum Size Subarray Sum (variable, shortest; positive numbers)
def min_subarray_len(target, nums):
left, total, best = 0, 0, float("inf")
for right, x in enumerate(nums):
total += x
while total >= target: # valid: shrink while it stays valid
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float("inf") else best
min_subarray_len(7, [2, 3, 1, 2, 4, 3]) → 2 ([4, 3]). Positivity matters: it’s what makes “remove from the left → sum goes down” true.
5. Find All Anagrams in a String (LeetCode 438): fixed window of counts
Every anagram of p is a window of length len(p) with the same character counts. Slide a fixed window, keep counts, and compare.
# 438. Find All Anagrams in a String (fixed window of counts)
def find_anagrams(s, p):
k, need, have, out = len(p), Counter(p), Counter(), []
for i, ch in enumerate(s):
have[ch] += 1
if i >= k:
old = s[i - k]
have[old] -= 1
if have[old] == 0:
del have[old]
if have == need:
out.append(i - k + 1)
return out
find_anagrams("cbaebabacd", "abc") → [0, 6]. Comparing two counters costs O(alphabet) per step; with a 26-letter array, or a running “matches” counter, it’s O(1). LeetCode 567 (Permutation in String) is the same code returning a boolean.
6. Minimum Window Substring (LeetCode 76): shortest
The classic hard problem. need holds how many of each character are still required; missing is the total still outstanding. When missing hits 0 the window covers t, so shrink from the left while it still does, recording the smallest.
# 76. Minimum Window Substring (variable, shortest)
def min_window(s, t):
need, missing = Counter(t), len(t)
left, best = 0, (0, float("inf"))
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if right - left < best[1] - best[0]:
best = (left, right)
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best[1] == float("inf") else s[best[0]: best[1] + 1]
min_window("ADOBECODEBANC", "ABC") → "BANC". Characters that aren’t in t go negative in need, which is exactly what lets the shrink step skip them.
7. Sliding Window Maximum (LeetCode 239): fixed window + monotonic deque
A running variable can’t tell you the maximum after the old maximum leaves. Keep a deque of indices whose values are decreasing: pop smaller values from the back when a new value arrives (they can never be the maximum again), and pop the front when it slides out.
# 239. Sliding Window Maximum (fixed window + monotonic deque)
def max_sliding_window(nums, k):
dq, out = deque(), []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return out
[1, 3, -1, -3, 5, 3, 6, 7] with k = 3 → [3, 3, 5, 5, 6, 7], in O(n). The sliding window maximum lesson has a full dry run and a Java version.
8. Subarrays with K Different Integers (LeetCode 992): counting windows
“Exactly k distinct” has no single shrink rule: a window with exactly k distinct values can be extended or shortened and still have k. So count with a trick: exactly(k) = atMost(k) − atMost(k − 1). For “at most”, every valid window ending at right contributes right - left + 1 subarrays.
# 992. Subarrays with K Different Integers (counting: exactly(K) = atMost(K) - atMost(K-1))
def subarrays_with_k_distinct(nums, k):
def at_most(k):
count, left, total = defaultdict(int), 0, 0
for right, x in enumerate(nums):
if count[x] == 0:
k -= 1
count[x] += 1
while k < 0:
count[nums[left]] -= 1
if count[nums[left]] == 0:
k += 1
left += 1
total += right - left + 1 # every window ending at `right` and starting in [left, right]
return total
return at_most(k) - at_most(k - 1)
[1, 2, 1, 2, 3] with k = 2 → 7. The same trick solves “count subarrays with exactly k odd numbers” (LeetCode 1248) and “binary subarrays with sum” (LeetCode 930).
Sliding window vs two pointers
Sliding window is a special case of two pointers, and the names get mixed up. The practical difference:
| Sliding window | Two pointers (opposite ends) | |
|---|---|---|
| Pointer movement | Both move forward, same direction | Start at both ends, move towards each other |
| What matters | Everything between the pointers | Usually just the two elements at the pointers |
| Input | Any array or string | Typically sorted, or symmetric (palindromes) |
| Examples | Longest substring without repeats, minimum window | Two Sum II, 3Sum, container with most water |
If the question is about the contents of a contiguous range, it’s a window. If it’s about a pair, and sorting helps, it’s opposite-end two pointers. The two pointers technique guide and the two pointers lesson cover the second family.
Sliding window vs prefix sums
“Subarray sum equals k” looks like a window problem but isn’t when numbers can be negative: adding a negative number can make an over-target window valid again, so you can’t decide when to shrink. Use a prefix sum plus a hash map of earlier prefix sums instead. The rule of thumb:
- All numbers non-negative and you want ≥ / ≤ a target → sliding window.
- Numbers can be negative, or you need an exact sum → prefix sums.
The prefix sum lesson works through this case.
Common mistakes
- Recording the answer in the wrong place. Longest: after the shrink loop. Shortest: inside it.
- Using
ifinstead ofwhileto shrink. One removal may not be enough to make the window valid again. - Forgetting to undo the summary when
leftmoves (decrement counts, delete zero-count keys if you compare dictionaries or use their size). - Applying it to negative numbers with an exact-sum condition (see above).
- Off-by-one window length. The window
[left, right]hasright - left + 1elements; a fixed window starts producing answers atright = k - 1.
Practice problems by difficulty
Work through these in order; each line names the variant.
| Problem | Variant | Difficulty |
|---|---|---|
| 643. Maximum Average Subarray I | Fixed | Easy |
| 1456. Max Vowels in a Substring of Given Length | Fixed | Medium |
| 3. Longest Substring Without Repeating Characters | Longest | Medium |
| 424. Longest Repeating Character Replacement | Longest | Medium |
| 1004. Max Consecutive Ones III | Longest | Medium |
| 209. Minimum Size Subarray Sum | Shortest | Medium |
| 438. Find All Anagrams in a String | Fixed + counts | Medium |
| 567. Permutation in String | Fixed + counts | Medium |
| 904. Fruit Into Baskets | At most 2 distinct | Medium |
| 992. Subarrays with K Different Integers | Counting | Hard |
| 76. Minimum Window Substring | Shortest | Hard |
| 239. Sliding Window Maximum | Fixed + deque | Hard |
Sliding window problems also appear, with progress tracking, on the Blind 75, LeetCode 150 and DSA sheet. The DSA patterns cheat sheet lists them all in one place.
FAQ
Is sliding window the same as two pointers?
It’s a kind of two pointers where both pointers move in the same direction and the elements between them matter. Classic two pointers starts at both ends of a sorted array and looks only at the pair.
What’s the time complexity of the sliding window algorithm?
O(n) for the pass, because each element is added once and removed at most once. Each add or remove must be O(1) (or O(log n) with a heap or sorted structure, giving O(n log n)).
How do I know if a problem needs a fixed or a variable window?
If the window length is given (k, or len(p) for anagrams), it’s fixed. If the question asks for the longest or shortest range satisfying a condition, it’s variable.
Can sliding window handle negative numbers?
For max/min sum of a fixed k, yes. For “longest/shortest subarray with sum ≥ / = target”, no: negatives break the shrink rule. Use prefix sums (with a monotonic deque for LeetCode 862).
Learn it step by step
- Sliding window lesson and sliding window maximum lesson in the free DSA Patterns course, with exercises and quizzes.
- The DSA patterns cheat sheet for the other 25+ patterns.