All patterns
Sliding Window
Grow and shrink a contiguous range while keeping a running summary.
time O(n)space O(1) to O(k)
What it is
Maintain a window [left, right] over a sequence. Extend right to include more, shrink left when a constraint breaks. Every index enters and leaves the window at most once, so the inner while loop is amortized O(1) per step.
When to reach for it
- Longest or shortest contiguous subarray or substring with a property
- Fixed size k windows (max sum, averages)
- Counting distinct elements in a range
Clues in the problem
- “Contiguous”, “substring”, “subarray”
- Condition becomes monotone as the window grows (all values non-negative, or a distinct-count limit)
- Nested loop where the inner start never needs to reset
Template
def longest_valid(a):left = best = 0state = {} # counts, running sum, ...for right, x in enumerate(a):state[x] = state.get(x, 0) + 1while violates(state): # shrink until valid againstate[a[left]] -= 1left += 1best = max(best, right - left + 1)return best
Practice problems
- Longest Substring Without Repeating Characters
- Minimum Size Subarray Sum
- Maximum Sum Subarray of Size K
- Fruit Into Baskets
Common mistakes
- Using it when values can be negative and the sum is not monotone (use prefix sums instead)
- Forgetting to update state when left moves
- Recomputing the window contents from scratch each step