DSA · Pattern
Sliding Window
Keep a window of elements in an array/string and slide it — great for subarrays and substrings with a size or sum limit.
Simple summary: Instead of checking every subarray from scratch (slow),
move a start and end pointer and update your count as the window slides.
Example: In
[2, 1, 5, 1, 3, 2], the max sum of 3 consecutive numbers is
5 + 1 + 3 = 9 — slide the window and add the new value minus the value that left.
1. When to use
- Maximum sum subarray of size k
- Longest substring without repeating characters
- Minimum window substring that contains all characters
- Any "contiguous block" problem with a constraint
2. Fixed-size window (size k)
Example: Array [2, 1, 5, 1, 3, 2], find max sum of any 3 consecutive numbers.
windowSum = sum(first k elements)
best = windowSum
for i from k to n-1:
windowSum += nums[i] - nums[i-k] // add new, remove old
best = max(best, windowSum)
return best
Walkthrough (k=3):
[2,1,5] → 8
slide: +1 -2 → [1,5,1] → 7
slide: +3 -1 → [5,1,3] → 9 ← best
slide: +2 -5 → [1,3,2] → 6
answer: 9
One pass → O(n) instead of O(n×k).
3. Variable-size window
Example: Longest substring without repeating letters in "abcabcbb".
left = 0, best = 0, seen = {}
for right in 0..n-1:
while s[right] is already in window:
remove s[left] from seen, left += 1
add s[right] to seen
best = max(best, right - left + 1)
return best
Walkthrough:
right=0 "a" → window "a", best=1
right=1 "b" → "ab", best=2
right=2 "c" → "abc", best=3
right=3 "a" repeats → shrink left → "bca", best stays 3
... longest valid window is "abc" → length 3
The right pointer always moves forward. The left pointer moves forward only when the window breaks a rule.
4. Fixed vs variable
| Fixed window | Variable window |
|---|---|
| Window size k is given | Window grows/shrinks by rule |
| Sum of k elements | Longest/shortest valid substring |
Quick revision
- Contiguous subarray/substring + limit → think sliding window.
- Fixed k: add right, subtract left-k.
- Variable: expand right; shrink left while invalid.
- Usually O(n) time.