roadmap/Sliding Window

Topic 3 / 16

Sliding Window

EasyArray~3 days
Easy to grasp
progress0 / 12 solved

Maintain a dynamic contiguous window to solve subarray/substring problems in O(n).

Concept

Maintain a dynamic window over a contiguous subarray or substring using two pointers. Expand the right pointer to grow the window; move the left pointer to shrink it when a constraint is violated. This avoids recomputing overlapping subarrays, reducing O(n²) nested loops to O(n).

When to use this pattern
  • ◆Longest or shortest subarray/substring with a constraint
  • ◆Fixed window size k — sum, max, average
  • ◆Problems with 'at most k distinct', 'without repeating', 'exactly k'
  • ◆Any optimization over contiguous elements
Common patterns
Fixed-size window
Slide a window of exactly k elements; maintain a running aggregate.
Variable-size window (max)
Expand right freely; shrink left when constraint breaks.
Variable-size window (min)
Shrink left aggressively once constraint is satisfied.
Window with frequency map
Track character/element counts inside the window using a HashMap.
Visual walkthrough
Sliding window — fixed size k=3
2
0
1
1
5
2
1
3
3
4
2
5
6
6
4
7
window[0..2]
→
sum = 8
step 1 / 6
Brute force → optimal thinking
Brute force
Generate all subarrays, check each one → O(n²) or O(n³) for strings.
Observation
Adjacent subarrays share most of their elements. Slide instead of restarting.
Optimization
Two pointers: right expands the window, left shrinks when the constraint is violated. Track state (sum/count/map) incrementally.
Final complexity
O(n) — each element enters and exits the window exactly once.
Quick Recall Check

When should you shrink the left side of a sliding window?

What is the time complexity of a well-implemented sliding window?

For a fixed-size window of k, how do you update the window as it slides?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Two Pointers
next
Stack
→
Progress is saved on this device