Fixed-Size Sliding Window

Foundations

In Two Pointers, left and right started at opposite ends and closed in. A sliding window moves both the same way, left to right. The window is the run from nums[left] to nums[right], both ends included, so it holds right - left + 1 elements, and a running value, such as their sum, summarizes them, the way Arrays & Strings carried one state through a scan.

There are two kinds. A fixed window always holds exactly k elements, so both edges step forward together and left = right - k + 1. A variable window lets the edges move separately: right takes in the next element, then left drops elements only while the window breaks its rule, such as a sum above 10. Neither edge ever moves backward, so each index enters once and leaves at most once: O(n) moves in all.

On nums = [7, 1, 5, 3, 6] with k = 3, the first fixed window covers indexes 0 to 2 and sums to 13. Sliding one step, nums[3] = 3 enters and nums[0] = 7 leaves, so the sum becomes 13 + 3 - 7 = 9 without adding 1 and 5 again. The next slide gives 9 + 6 - 1 = 14. Each slide costs two operations, however large k is.

• In-Place Read & Write Pointers

  That lesson moves read and write in the same direction. A window's left and right move the same way, and the elements between them are the window.

  Open lesson

Case Scenario

Maximum Average Subarray I is a fixed window with k given: each run of exactly k elements is one window position, and its average is its sum divided by k. With k fixed, the largest sum has the largest average, so the scan tracks sums and divides once at the end. In nums = [1, 12, -5, -6, 50, 3] with k = 4, the best window, indexes 1 to 4, sums to 51, and 51 / 4 = 12.75.

The direct approach sums every window from scratch: for each i, an inner loop adds nums[i] through nums[i + k - 1], and the largest total wins. That is n - k + 1 windows of k additions each, O(n · k): 12 additions here, but about 2.5 billion for n = 100,000 and k = 50,000. Step through the windows below to see how much of each sum the window before it already added.