Sliding Window
Curriculum
A structured path to mastering the sliding window pattern. Track contiguous subarrays with dynamic boundaries and state.
What This Pattern Is Really About
Window expands to explore new elements and contracts when constraints are violated. Boundaries move independently based on validity.
Maintain window properties incrementally—sum, frequency, distinct count. Update state as elements enter and exit the window.
Window is either valid (satisfies constraint) or being adjusted. Expand when valid, contract when invalid. Binary state drives movement.
Each element enters the window once and exits once. O(n) time guaranteed—no nested loops, no backtracking.
Mental Model & Invariant
Sliding window is a moving frame over contiguous elements.
"At any moment, the window either satisfies the constraint or is being adjusted to satisfy it. All elements outside the window have been processed and cannot improve the current solution."
Break this, and you miss valid solutions or examine invalid regions.
When It Holds
Before expansion, after contraction, and at every boundary update. If violated, your window logic is incorrect.
Movement Rule
Expand right to explore. Contract left when invalid. State updates must reflect boundary changes immediately.
Termination
When right pointer reaches the end, all possible windows have been examined. Either optimal solution found or none exists.
When to Think "Sliding Window"
sensorsStrong Signals
Contiguous subarray or substring
Longest/shortest with constraint
At most K distinct elements
Maximum/minimum sum of size K
All subarrays satisfying property
Running state can be tracked incrementally
ruleConstraint Signals
Must solve in linear time
Cannot use nested loops
State updates are O(1)
Boundaries move monotonically
Variants You Must Master
Fixed-Size Window
Window size is constant. Slide by removing left and adding right.
Window always contains exactly K elements.
Variable-Size Window
Expand until invalid, then contract until valid again.
Window is valid or being adjusted.
Two-Pointer Variant
Left and right move independently based on validity.
All valid windows examined or recorded.
Monotonic Window
Maintain monotonic property within window using deque.
Deque tracks min/max candidates.
How to Learn This Pattern
Define Window Validity
Write down what makes a window valid. What constraint must hold? What state tracks this?
Identify State Updates
How does state change when element enters? When element exits? Must be O(1) operations.
Determine Movement Logic
When do you expand? When do you contract? What triggers each boundary movement?
Trace Fixed-Size First
Start with fixed window size K. Slide by removing left, adding right. Verify state updates.
Progress to Variable-Size
Expand while valid, contract while invalid. Track optimal window during traversal.
Verify Edge Cases
Empty input, single element, all invalid, all valid. Confirm invariant holds throughout.
Canonical Problem List
Fixed Window
Window size K is constant. Slide by removing i-K and adding i.
Variable Window
Expand right until invalid; then contract left until valid again.
Monotonic Window
Maintain max/min candidate in deque. Remove useless elements.
folder_openFoundation
Maximum Sum Subarray of Size K
Direct fixed-window application; establishes the slide-by-removing-and-adding pattern.
Average of Subarrays of Size K
Same fixed window; reinforces that state updates must be O(1) per step.
Maximum of All Subarrays of Size K
Introduces monotonic deque to track the sliding maximum efficiently.
First Negative in Every Window of Size K
Queue-based tracking of negative numbers within a fixed window.
folder_openIntermediate
Longest Substring with At Most K Distinct Characters
Variable window; contract when map size exceeds K.
Max Consecutive Ones III
Variable window; count of zeros in window ≤ K drives contraction.
Longest Repeating Character Replacement
Variable window; windowSize − maxFreq ≤ K is the validity condition.
Subarray Product Less Than K
Variable window; product ≥ K triggers left contraction.
folder_openAdvanced
Minimum Window Substring
All target characters must be present with required frequency; contract to minimize.
Longest Substring Without Repeating Characters
All characters in window must be unique; jump left pointer on repeat.
Subarrays with K Different Integers
Exact-K trick: atMost(K) − atMost(K−1) using two sliding windows.
Permutation in String
Character frequency must match target pattern in fixed-size window.
Minimum Size Subarray Sum
Sum ≥ target; minimize window by contracting as soon as condition holds.
Common Mistakes
Not Updating State Correctly
Window state becomes stale; validity checks fail; wrong answers returned.
Update state immediately when element enters or exits. Verify state reflects current window.
Incorrect Shrinking Logic
Window contracts too early or too late; misses optimal solutions or examines invalid regions.
Contract only when invalid. Use while loop for contraction, not if statement.
Off-by-One in Window Boundaries
Window size calculation wrong; includes or excludes wrong elements.
Window size is (right - left + 1). Verify with small examples.
Forgetting to Track Optimal
Find valid windows but don't record the best one; return wrong answer.
Update optimal solution whenever valid window found. Track max/min explicitly.
Confusing Fixed vs Variable Window
Use wrong expansion/contraction logic; algorithm doesn't match problem type.
Fixed: slide by +1 each step. Variable: expand until invalid, then contract.
Interview Guidance
What they test
- →Window Validity Definition
- →State Management Precision
- →Boundary Movement Justification
Strategy
Avoid "I'll use sliding window" without context. Instead: "I need to track contiguous elements with a constraint, so I'll maintain a window that expands when valid and contracts when invalid."
The Verbal Template
"A window is valid when [constraint holds]. I track this using [state]."
"I expand right to include new elements and update state by [operation]."
"When invalid, I contract left until valid again, updating state by [operation]."
"I track the best window seen so far and update when [condition]."
When You've Mastered It
Immediate window type recognition
State defined before coding
Validity condition articulated clearly
Boundary logic justified precisely
Edge cases handled analytically
Flawless state update implementation
What This Unlocks Next
Monotonic Stack/Deque
Extends window concept with monotonic property tracking for extrema.
Dynamic Programming
Sliding window optimizes DP state transitions for contiguous subproblems.
Two Pointers
Generalizes to non-contiguous element pairing and partitioning.
Streaming Algorithms
Real-world application in rate limiting, buffering, and time-series analysis.