Topic Lesson
Learn Sliding Window from scratch
A complete 4-step path: handwritten notebook primer, animated visualizer, speed check quiz, and compiler practice.
What is Sliding Window
notebook noteA sliding window is an adjustable magnifying lens placed over a continuous segment of a sequence. Rather than recalculating metrics for every potential subsection from scratch, the window expands rightward by absorbing fresh elements and contracts leftward to expel stale entries. Only data currently framed within the window borders contributes to the active calculation.
When to reach for it
Reach for a sliding window when a question asks for the longest, shortest, or optimal contiguous subarray or substring matching a constraint. Key signals include fixed window sizes like maximum sum across k consecutive values, or dynamic criteria like finding the shortest substring holding all target characters. If the target subset must form an unbroken continuous run, window mechanics replace repetitive segment rescanning.
How to think about it
Maintain two boundary indices, left and right, defining the active interval alongside a running state accumulator. In each step, expand the right boundary to incorporate the incoming element into state totals. When current state violates the designated problem constraints, increment the left boundary while deducting departing values until validity is restored. Update your tracking metric, whether minimum window length or maximum score, only during valid intervals.
Operation costs
measured big-O| Operation | Time |
|---|---|
| slide window across full array length | O(n) |
| update running aggregate per incoming element | O(1) |
| auxiliary window frequency map storage | O(k) |
Common mistakes to avoid
- Shrinking the left border using an if statement instead of a while loop, allowing invalid window conditions to persist across iterations.
- Updating optimum results before validating window legality, recording illegal states that contain duplicate items or violate length requirements.
- Forgetting to decrement left element frequencies or remove empty keys from tracking maps when advancing the left boundary forward.