The sliding window
Turn an O(n·k) scan into a single O(n) pass by reusing the overlap. · 6 min read
Many array problems ask about every contiguous block of some size — the maximum sum of k in a row, the longest substring without repeats, and so on. The naive approach recomputes each block from scratch: O(n·k).
The sliding window is smarter. As the window moves one step right it adds the new element and drops the old one — reusing everything in between. That makes it a single O(n) pass:
Interactive visualization: Max sum of k consecutive elements — step through it frame by frame on this page.
Why the window is linear
first window costs k— Build the initial sum once.each slide costs 2 updates— Add the new right item, subtract the old left item.there are n−k slides— The right edge moves across the rest of the array.k + 2(n−k)— Total work is still a constant amount per item.
Result: O(n)
Practice: Longest Substring Without Repeating (Medium) — Sliding window over a string with a last-seen map.