Algorithms
Sliding Window Technique
Maintain a running window over a contiguous subarray or substring — expand it to include more, shrink it to restore a constraint. Every element enters and exits the window at most once, giving O(n) where brute force needs O(n²).
Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation
What is Sliding Window?
Sliding window maintains a contiguous subarray (or substring) bounded by two pointers — left and right. The right pointer expands the window to include more elements; the left pointer contracts it to restore a violated constraint. The crucial insight: instead of recomputing the window's aggregate (sum, count, frequency map) from scratch each time, you incrementally update it — add the new element entering on the right, remove the old element exiting on the left. Each element enters the window once and exits once → O(n) total, regardless of window size. The technique comes in two flavours: fixed-size windows (maximum sum of subarray with exactly k elements) and variable-size windows (smallest subarray whose sum ≥ target, longest substring without repeating characters). Fixed windows always have size k; variable windows expand until a condition is met, then shrink until it's violated, tracking the best result at each valid state.
Analogy: Reading a book through a magnifying strip that shows exactly 3 lines at a time. To see the next line, you don't re-read lines 1 through 4 — you slide the strip down one line: line 1 disappears from the top, line 4 appears at the bottom. The "cost" of each slide is O(1) — you process only the one line entering and the one line leaving, not the entire visible window. That's the sliding window: incremental updates instead of full recomputation.
02
Section Two · Mental Model
How It Thinks
The problem asks about CONTIGUOUS subarrays or substrings
▶
Elements of interest form a window [left, right] — any subarray question on contiguous elements is a sliding window candidate
The window aggregate (sum, count, frequency) can be updated incrementally in O(1)
▶
Expanding: add arr[right]. Shrinking: subtract arr[left]. No need to re-sum the entire window — O(1) per step, O(n) total
Fixed-size window: k is given, window is always exactly k elements
▶
Right pointer advances every step; left = right - k + 1 follows automatically. Compute answer at each position where window is full
Variable-size window: condition determines when to shrink
▶
Expand right until condition is met → record answer → shrink left until condition is violated → expand right again. Track best answer across all valid windows
String problems use a frequency map (int[128] or HashMap) as the window state
▶
Character enters: increment count. Character exits: decrement count. "All unique" = no count exceeds 1. "Contains all of t" = all required counts are met
Both pointers move monotonically forward — left never moves backward
▶
Each element is added once (when right passes it) and removed once (when left passes it) — amortised O(n) even though the inner while loop may run multiple times per step
03
Section Three · Fixed Window
Pattern 1 — Fixed-Size Window
The window is always exactly k elements wide. Build the initial window of size k, then slide one position at a time — add the new element on the right, remove the old element on the left. Update the answer at each step. This is the simplest sliding window pattern.
Maximum Sum Subarray of Size K
Find the contiguous subarray of exactly k elements with the maximum sum.
Pseudocode
function maxSumK(arr, k):
windowSum = sum(arr[0..k-1]) // build initial window
maxSum = windowSum
for right = k to arr.length - 1:
windowSum += arr[right] // add new element
windowSum -= arr[right - k] // remove old element
maxSum = max(maxSum, windowSum)
return maxSum // O(n)
Fixed window k=3 sliding across [2, 1, 5, 3, 7, 4]
Fixed window is dead simple — no shrinking decision:
- The window always has exactly k elements. Just slide and track the best.
- The only variation is what you track: maximum sum, maximum average, count of distinct elements, etc.
04
Section Four · Variable Window
Pattern 2 — Variable-Size Window
The window size varies — expand the right end to include more elements until a constraint is met (or violated), then shrink the left end to restore (or break) the constraint. Track the best valid window seen so far. This pattern handles "minimum length subarray with sum ≥ S" and "longest substring with at most K distinct characters."
The Universal Variable-Window Template
Template
int left = 0;
int best = 0; // or Integer.MAX_VALUE for minimum problems // window state: sum, count, frequency map, etc. for (int right = 0; right < n; right++) {
// ① EXPAND: add arr[right] to window state while (windowIsInvalid()) { // or "while valid" for minimum problems // ② SHRINK: remove arr[left] from window state
left++;
}
// ③ UPDATE: best = max(best, right - left + 1)
}
Minimum Size Subarray Sum (LC 209)
Find the shortest contiguous subarray whose sum ≥ target. Return its length, or 0 if impossible.
Pseudocode
function minSubArrayLen(target, arr):
left = 0, sum = 0, minLen = ∞
for right = 0 to arr.length - 1:
sum += arr[right] // expand while sum >= target: // condition met!
minLen = min(minLen, right - left + 1)
sum -= arr[left] // shrink to find shorter
left = left + 1 return minLen == ∞ ? 0 : minLen // O(n)
Variable window — target=7 on [2, 3, 1, 2, 4, 3]
Common Mistake: Thinking the inner
while loop makes it O(n²). It doesn't — the left pointer only moves forward, and it moves at most n times total across ALL iterations of the outer loop. Total work: right moves n times + left moves at most n times = O(2n) = O(n). This is the amortised analysis that makes sliding window O(n).
05
Section Five · String Windows
Sliding Window on Strings
String sliding window problems use a frequency map as the window state — typically int[128] for ASCII characters or a HashMap<Character, Integer>. The key mechanics: when a character enters the window (right advances), increment its count. When it exits (left advances), decrement its count. The "constraint" is usually about character uniqueness or required character frequencies.
Longest Substring Without Repeating Characters (LC 3)
Find the length of the longest substring where all characters are unique.
Pseudocode
function lengthOfLongestSubstring(s):
freq = new int[128] // ASCII frequency map
left = 0, maxLen = 0 for right = 0 to s.length - 1:
freq[s[right]]++ // character enters while freq[s[right]] > 1: // duplicate in window!
freq[s[left]]-- // character exits
left = left + 1
maxLen = max(maxLen, right - left + 1)
return maxLen // O(n)
Alternative: use a HashMap storing last-seen index.:
- When you encounter a repeated character, jump left directly to
lastSeen[c] + 1instead of shrinking one step at a time. - Same O(n) complexity but fewer iterations in practice:
left = max(left, map.get(c) + 1).
06
Section Six · With HashMap
Advanced — Window With Frequency Counts
The hardest sliding window problems — like "Minimum Window Substring" (LC 76) — require tracking whether the window satisfies a complex condition involving multiple characters. The pattern: maintain a frequency map of required characters, a frequency map of window characters, and a counter tracking how many required characters have their full count satisfied. When the counter equals the number of distinct required characters, the window is valid.
Minimum Window Substring (LC 76)
Given strings s and t, find the shortest substring of s that contains all characters of t (including duplicates).
Pseudocode
function minWindow(s, t):
need = frequencyMap(t) // required counts
window = {} // current window counts
have = 0, required = need.size // distinct chars needed
left = 0, bestLen = ∞, bestStart = 0 for right = 0 to s.length - 1:
c = s[right]
window[c]++
if c in need and window[c] == need[c]:
have++ // one more char fully satisfied while have == required: // window contains all of t if right - left + 1 < bestLen:
bestLen = right - left + 1
bestStart = left
d = s[left]
window[d]--
if d in need and window[d] < need[d]:
have-- // lost a required char
left++
return bestLen == ∞ ? "" : s[bestStart..bestStart + bestLen]
// O(|s| + |t|)
The "have" counter is the key optimisation:
- Without it, you'd check all 26+ characters every time to see if the window is valid — O(26) per step.
- With the "have" counter that increments/decrements when a character reaches/drops below its required count, validity checking is O(1).
- This is what makes LC 76 tractable.
07
Section Seven · When to Use
Recognising Sliding Window Problems
| Signal in Problem | Window Type | Examples |
|---|---|---|
| "maximum/minimum subarray of size k" | Fixed | Max sum subarray, max average |
| "shortest/smallest subarray with sum ≥ X" | Variable (shrink when valid) | Min size subarray sum (LC 209) |
| "longest substring with at most K distinct" | Variable (shrink when invalid) | Longest with K distinct (LC 340) |
| "longest substring without repeating" | Variable (shrink when invalid) | Longest without repeat (LC 3) |
| "smallest window containing all of t" | Variable (shrink when valid) | Min window substring (LC 76) |
| "count of subarrays with exactly K" | Variable (atMost(K) - atMost(K-1)) | Subarrays with K distinct (LC 992) |
Shrink when VALID
Finding MINIMUM window
Expand until condition is met ✓ → record/update answer → shrink to find a shorter valid window → keep shrinking while still valid
- Min size subarray sum ≥ target
- Min window substring
Shrink when INVALID
Finding MAXIMUM window
Expand until condition is violated ✗ → shrink until condition is restored ✓ → record/update answer → expand again
- Longest substring without repeating
- Longest with at most K distinct
Sliding window vs two pointers:
- Sliding window IS a specialised form of two pointers — both use left and right indices.
- The distinction: sliding window maintains a running "window state" (sum, frequency map, count) that is incrementally updated.
- Two pointers (opposite ends) does not maintain state between the two pointers — it makes a decision based on the values at L and R directly.
08
Section Eight · Implementation
Build It Once
Build the fixed and variable templates once. The code is short — the challenge is recognising which template applies and what "window state" to maintain.
Java — Fixed & Variable window core
// Fixed window — max sum of size k — O(n) int maxSumK(int[] arr, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int max = sum;
for (int r = k; r < arr.length; r++) {
sum += arr[r] - arr[r - k];
max = Math.max(max, sum);
}
return max;
}
// Variable window — min length with sum ≥ target — O(n) int minSubArrayLen(int target, int[] arr) {
int left = 0, sum = 0, min = Integer.MAX_VALUE;
for (int r = 0; r < arr.length; r++) {
sum += arr[r];
while (sum >= target) {
min = Math.min(min, r - left + 1);
sum -= arr[left++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
// String window — longest without repeating — O(n) int lengthOfLongestSubstring(String s) {
int[] freq = new int[128];
int left = 0, max = 0;
for (int r = 0; r < s.length(); r++) {
freq[s.charAt(r)]++;
while (freq[s.charAt(r)] > 1)
freq[s.charAt(left++)]--;
max = Math.max(max, r - left + 1);
}
return max;
}
Sliding Window — Full Implementation
Java — All sliding window patterns
import java.util.*;
public class SlidingWindow {
// ═══ 1. Fixed — max sum of size k ════════ O(n) static int maxSumK(int[] arr, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int max = sum;
for (int r = k; r < arr.length; r++) {
sum += arr[r] - arr[r - k];
max = Math.max(max, sum);
}
return max;
}
// ═══ 2. Variable — min subarray sum ≥ target O(n) static int minSubArrayLen(int target, int[] arr) {
int left = 0, sum = 0, min = Integer.MAX_VALUE;
for (int r = 0; r < arr.length; r++) {
sum += arr[r];
while (sum >= target) {
min = Math.min(min, r - left + 1);
sum -= arr[left++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
// ═══ 3. Longest substring without repeat ═ O(n) static int lengthOfLongestSubstring(String s) {
int[] freq = new int[128];
int left = 0, max = 0;
for (int r = 0; r < s.length(); r++) {
freq[s.charAt(r)]++;
while (freq[s.charAt(r)] > 1)
freq[s.charAt(left++)]--;
max = Math.max(max, r - left + 1);
}
return max;
}
// ═══ 4. Longest with at most K distinct ══ O(n) static int longestKDistinct(String s, int k) {
Map<Character, Integer> freq = new HashMap<>();
int left = 0, max = 0;
for (int r = 0; r < s.length(); r++) {
freq.merge(s.charAt(r), 1, Integer::sum);
while (freq.size() > k) {
char c = s.charAt(left++);
freq.merge(c, -1, Integer::sum);
if (freq.get(c) == 0) freq.remove(c);
}
max = Math.max(max, r - left + 1);
}
return max;
}
// ═══ 5. Minimum window substring ═════════ O(|s|+|t|) static String minWindow(String s, String t) {
int[] need = new int[128], window = new int[128];
int required = 0;
for (char c : t.toCharArray())
if (need[c]++ == 0) required++;
int left = 0, have = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
window[c]++;
if (need[c] > 0 && window[c] == need[c]) have++;
while (have == required) {
if (r - left + 1 < bestLen) {
bestLen = r - left + 1;
bestStart = left;
}
char d = s.charAt(left++);
if (need[d] > 0 && window[d] == need[d]) have--;
window[d]--;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
// ═══ 6. Max consecutive ones with K flips ═ O(n) static int longestOnes(int[] arr, int k) {
int left = 0, zeroes = 0, max = 0;
for (int r = 0; r < arr.length; r++) {
if (arr[r] == 0) zeroes++;
while (zeroes > k)
if (arr[left++] == 0) zeroes--;
max = Math.max(max, r - left + 1);
}
return max;
}
// ═══ Main ═══════════════════════════════════ public static void main(String[] args) {
System.out.println(maxSumK(new int[]{2,1,5,3,7,4}, 3)); // 15 System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3})); // 2 System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3 System.out.println(minWindow("ADOBECODEBANC", "ABC")); // "BANC" System.out.println(longestOnes(new int[]{1,1,0,0,1,1,1,0,1}, 2)); // 7
}
}
Python — Sliding window implementations
from collections import defaultdict, Counter
# ═══ 1. Fixed — max sum of size k ════════ O(n) def max_sum_k(arr, k):
s = sum(arr[:k])
best = s
for r in range(k, len(arr)):
s += arr[r] - arr[r - k]
best = max(best, s)
return best
# ═══ 2. Variable — min subarray sum ≥ target O(n) def min_sub_len(target, arr):
left = s = 0
best = float('inf')
for r in range(len(arr)):
s += arr[r]
while s >= target:
best = min(best, r - left + 1)
s -= arr[left]; left += 1
return best if best != float('inf') else 0
# ═══ 3. Longest substring without repeat ═ O(n) def length_of_longest(s):
freq = defaultdict(int)
left = best = 0
for r, c in enumerate(s):
freq[c] += 1
while freq[c] > 1:
freq[s[left]] -= 1; left += 1
best = max(best, r - left + 1)
return best
# ═══ 4. Longest with at most K distinct ══ O(n) def longest_k_distinct(s, k):
freq = defaultdict(int)
left = best = 0
for r, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
best = max(best, r - left + 1)
return best
# ═══ 5. Minimum window substring ═════════ O(|s|+|t|) def min_window(s, t):
need = Counter(t)
window = defaultdict(int)
have, required = 0, len(need)
left, best = 0, (float('inf'), 0, 0)
for r, c in enumerate(s):
window[c] += 1
if c in need and window[c] == need[c]:
have += 1
while have == required:
if r - left + 1 < best[0]:
best = (r - left + 1, left, r + 1)
d = s[left]
window[d] -= 1
if d in need and window[d] < need[d]:
have -= 1
left += 1
return s[best[1]:best[2]] if best[0] != float('inf') else "" # ═══ 6. Max consecutive ones with K flips ═ O(n) def longest_ones(arr, k):
left = zeroes = best = 0
for r in range(len(arr)):
if arr[r] == 0: zeroes += 1
while zeroes > k:
if arr[left] == 0: zeroes -= 1
left += 1
best = max(best, r - left + 1)
return best
# Demo
print(max_sum_k([2,1,5,3,7,4], 3)) # 15
print(min_sub_len(7, [2,3,1,2,4,3])) # 2
print(length_of_longest("abcabcbb")) # 3
print(min_window("ADOBECODEBANC", "ABC")) # "BANC"
print(longest_ones([1,1,0,0,1,1,1,0,1], 2)) # 7
09
Section Nine · Java Reference
Use It In Java
IN JAVA — Sliding Window Idioms
Frequency
int[] freq = new int[128]; — fastest for ASCII chars, O(1) lookup HashMap
Map<Character, Integer> map = new HashMap<>(); — use merge(c, 1, Integer::sum) Characters
s.charAt(i) — returns char, usable as array index for int[128] | Idiom | Use case | Note |
|---|---|---|
freq[s.charAt(r)]++ | Character enters window | O(1) — direct array indexing with char |
freq[s.charAt(left++)]-- | Character exits window | Decrement and advance left in one line |
map.merge(c, 1, Integer::sum) | Increment count in HashMap | Cleaner than getOrDefault + put |
map.merge(c, -1, Integer::sum) | Decrement count | Follow with if (map.get(c)==0) map.remove(c) |
Math.max(max, r - left + 1) | Update longest window | Window length = right - left + 1 |
Integer.MAX_VALUE | Initial value for "minimum" problems | Check at end: min == MAX_VALUE ? 0 : min |
⚠ Gotcha: When using a HashMap for frequency counts and checking
map.size() for "number of distinct characters," you must remove keys when their count drops to 0 — otherwise size() includes characters that are no longer in the window. Use if (map.get(c) == 0) map.remove(c) after decrementing.
⚠ Gotcha:
int[128] is faster than HashMap for ASCII-only problems — no boxing, no hashing, no collision handling. Use it for all lowercase/uppercase/ASCII sliding window string problems. Reserve HashMap for Unicode or when you need .size() for distinct-count tracking.
10
Section Ten · Practice
Problems To Solve
Sliding window problems all share one signal: "contiguous subarray/substring" + an aggregate condition (sum, count, uniqueness). Fixed-size problems are easy warm-ups. Variable-size problems are the real interview challenges — the hardest part is deciding WHEN to shrink: shrink when valid (minimum problems) or shrink when invalid (maximum problems). Once you internalise this distinction, every sliding window problem is the same template with a different window state and shrink condition.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Easy | fixed | Maximum Average Subarray I — LC 643 | Fixed window of size k. Track running sum, compute average at each position. Pure fixed template. |
| Medium | variable | Longest Substring Without Repeating — LC 3 | Variable window + frequency array. Shrink when a character's count exceeds 1 (invalid). Track max window length. |
| Medium | variable | Minimum Size Subarray Sum — LC 209 | Variable window. Shrink when sum ≥ target (valid) — record length, keep shrinking. Track min window length. |
| Medium | variable | Max Consecutive Ones III — LC 1004 | Variable window allowing at most k zeroes. Window state: count of zeroes. Shrink when zeroes > k. Track max window length. |
| Medium | variable | Permutation in String — LC 567 | Fixed-ish window of size len(s1) on s2. Compare frequency arrays at each position. Alternatively, use a "matches" counter. |
| Hard | hashmap | Minimum Window Substring — LC 76 | Variable window + need/have counters. Shrink when all required characters are satisfied (valid). Track minimum valid window. |
Interview Pattern:
- Read the problem. See "contiguous subarray" or "substring"? → Sliding window.
- See "sum ≥ target" or "at most K distinct"? → Variable window. See "of size K"? → Fixed window.
- Then: (1) decide what state the window tracks (sum, frequency map, count), (2) decide when to shrink (valid → minimum, invalid → maximum), (3) write the template.
- Done.