Back to Topics
Sliding Window
Sliding window is a technique for reducing a nested loop over subarrays/substrings to a single O(n) pass. You maintain a window defined by two pointers (left, right) and expand or shrink it based on a constraint. It is the go-to pattern whenever the problem asks for a contiguous subarray or substring satisfying some condition.
Key Ideas
- Fixed window: advance left and right together, keeping window size constant
- Variable window: expand right until constraint is violated, then shrink from left
- A hash map or counter inside the window tracks the current state efficiently
- The window never needs to restart from the beginning — each element is added/removed at most once, giving O(n) total
- Applicable when the problem has optimal substructure on contiguous ranges
Complexity
| Operation | Time | Space |
|---|---|---|
| Fixed-size window scan | O(n) | O(1) |
| Variable window scan | O(n) | O(k) |
| Window with frequency map | O(n) | O(k) |
Common Patterns
Fixed WindowWindow size k is constant — track a running sum/product and subtract the outgoing element.
Variable Window (shrink on violation)Expand right freely; when constraint breaks, advance left to restore validity.
Minimum WindowFind smallest window containing all required elements; use two counters — need vs. have.
Code Example
Longest substring without repeating characterspython
def length_of_longest_substring(s: str) -> int:
char_index: dict[str, int] = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in char_index and char_index[ch] >= left:
left = char_index[ch] + 1 # shrink: skip past duplicate
char_index[ch] = right
best = max(best, right - left + 1)
return best💡
If the brute-force is O(n²) because of a nested loop over start/end indices, the problem is likely a sliding window.