Sliding window: definition
Maintain a contiguous section of an array or string and update its state as the boundaries move. Reuse the previous work instead of rebuilding each overlapping section.
Fixed-size windows keep a length such as k. Variable-size windows grow or shrink to satisfy a condition. A valid boundary rule is essential; not every subarray problem supports sliding window.
Problems this pattern can solve
- Maximum average of k consecutive values
- Longest substring without repeated characters
- Smallest positive-number subarray reaching a target sum
- Find a permutation of a string inside another string
Task example: Maximum Average Subarray I
Given nums and k, return the largest average of any contiguous subarray of exactly k elements. Keep the original order. Require 1 <= k <= len(nums).
For k = 4, the three sums are 2, 51, and 42. The best window is [12, -5, -6, 50]: 51 / 4 = 12.75.
Do not sort or skip values. k = 1 selects the largest element; k = n uses the whole array. Negative averages are valid.
Brute force: video explanation
nums = [1, 12, -5, -6, 50, 3], k = 4 → 12.75
Prefer reading? Follow the steps below.
- Try each start from 0 through n - k. Reset total to 0 and add the next k consecutive values with an inner loop.
- Keep the largest complete window sum. Start best at negative infinity so an all-negative array is handled correctly.
- Compare sums 2, 51, and 42, then divide the best by k. All windows have the same positive length, so the largest sum also gives the largest average.
Time complexity · O((n - k + 1)k)
There are n - k + 1 windows, each summing k values: O((n - k + 1)k), bounded by O(nk). The worst case over k is quadratic.
Space complexity · O(1)
Only indices, total, and best are stored. The code uses loops rather than array slices, so extra space is O(1).
Sliding window: video explanation
nums = [1, 12, -5, -6, 50, 3], k = 4 → 12.75
Prefer reading? Follow the steps below.
- Sum the first k values without slicing and set best to that sum. This also handles negative inputs correctly.
- For each new right index, subtract nums[right - k], then add nums[right]. Update best after both operations, when the window has k elements again.
- The sum changes from 2 to 2 - 1 + 50 = 51, then to 51 - 12 + 3 = 42. Return 51 / 4 = 12.75.
Why it works: neighboring windows share k - 1 values. Removing the outgoing value and adding the incoming one preserves the current sum. We avoid rebuilding sums without skipping any window.
Time complexity · O(n)
The first window takes O(k). Each of the remaining n - k shifts takes O(1), for O(n) total time.
Space complexity · O(1)
Only a few indices and sums are stored. No copied window or extra array is created: O(1) extra space.