Sliding Window

Sliding window is two pointers' close cousin: instead of moving toward each other, both pointers move in the same direction together, framing a contiguous "window" over the array or string as they go.

The naive approach to "find the maximum sum of any k consecutive elements" re-sums every window from scratch, O(n * k) overall, which becomes O(n²) once k scales with n. A sliding window instead computes the first window's sum once, then slides one position at a time by subtracting the element that just left the window and adding the element that just entered it, O(1) work per slide instead of O(k).

The total cost is the initial O(k) sum plus one O(1) update per remaining position, giving O(n) overall, versus O(n * k) for re-summing every window from scratch.

Not every window problem has a fixed size. A problem like finding the longest substring without any repeated characters needs a window that grows while its contents stay valid, and shrinks from the left the moment a repeat appears, tracking the best length seen along the way. The general shape uses two pointers: a right pointer that always advances, expanding the window by including one more element, and a left pointer that only advances when the window becomes invalid, contracting it back to validity. Both pointers only ever move forward, never backward, which is exactly what keeps this O(n) instead of O(n²), since every element is added to the window at most once and removed from it at most once, in total.

Tracing longest_subarray_at_most([2, 1, 3, 4, 1], 6): at right = 0, window_sum = 2, valid, best_length = 1. At right = 1, window_sum = 3, valid, best_length = 2. At right = 2, window_sum = 6, still valid, best_length = 3. At right = 3, window_sum = 10, too big, so the window contracts from the left. Subtracting items[0] = 2 gives 8, still too big. Subtracting items[1] = 1 gives 7, still too big. Subtracting items[2] = 3 gives 4, now valid, with left now at index 3, and best_length stays 3 (this window has length 1). At right = 4, window_sum = 5, valid, and the window (indices 3 to 4) has length 2, so best_length remains 3. The final answer is 3, matching the subarray [2, 1, 3].