The sliding window pattern converts O(n²) subarray problems into O(n). Instead of re-scanning from scratch every time, you maintain a window of elements and update it incrementally — adding one element to the right, removing one from the left.
There are two variants: fixed-size (slide a window of constant width k across the array) and variable-size (expand right until a condition is met, then shrink from the left to optimise).
The window is just two pointers — left and right — defining which elements are currently 'in scope'. You don't store the elements separately, you just track the boundaries.
Instead of recomputing the sum of k elements every step (O(k)), sliding window does: sum = sum - arr[left] + arr[right+1]. One operation per slide — O(1).
Both left and right pointers only ever move rightward. Each element is added once and removed at most once. Total operations: 2n. That's O(n) regardless of window size.
Fixed: window size k is given, slide one step at a time. Variable: no fixed size — expand right to satisfy a condition, shrink left to optimise, track the best window seen.
TIPThe key insight for variable window: right only moves forward, left only moves forward. Each element enters the window once and leaves at most once. That's why it's O(n) even with the while loop inside the for loop.
COLOUR LEGEND
Window expanding (right moves) Window shrinking (left moves)