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].