Sliding Window
Quick reference
| Fixed-size window | O(n) |
| Variable-size window | O(n) amortized |
| Recomputing every subarray from scratch (for comparison) | O(n²) or worse |
A window is a continuous part of the array. It has a start edge and an end edge. Everything between them is in the window. Think about a question such as "what is the best sum of any 5 consecutive elements". The brute-force method checks each possible part from the start. For each start point, it moves forward and adds each element in that part again. This method computes the same elements many times. Sliding window keeps one window and moves it. The end edge moves forward to add a new element. The start edge moves forward to drop an old element. A running total gets one small update instead of a full rebuild.
This method has two shapes. A fixed-size window always covers exactly k elements. It moves one step at a time. It gains one element on the right and loses exactly one element on the left. A variable-size window grows and becomes smaller based on a condition. Expand the right edge while the window is valid. When the window stops being valid, make it smaller from the left until it is valid again.
Window shapes
// Fixed-size window of width k
windowSum = sum of the first k elements
for right from k to length - 1:
windowSum += arr[right] // the element that enters on the right
windowSum -= arr[right - k] // the element that leaves on the left
... use windowSum ...
// Variable-size window
left = 0
for right from 0 to length - 1:
... add arr[right] to the running state of the window ...
while the window is invalid:
... remove arr[left] from the running state of the window ...
left += 1
... the window [left, right] is now valid. Use it. ...fixed-size window — maintain a running aggregate
function maxFixedWindowSum(arr, k):
windowSum = 0
for i from 0 to k - 1:
windowSum += arr[i] // build the first window directly
best = windowSum
for right from k to length(arr) - 1:
windowSum += arr[right] // the element that enters
windowSum -= arr[right - k] // the element that leaves
best = max(best, windowSum)
return bestvariable-size window — grow, then shrink until valid again
function smallestWindowAtLeastTarget(arr, target):
left = 0
windowSum = 0
best = infinity
for right from 0 to length(arr) - 1:
windowSum += arr[right] // grow: always add the new right edge
while windowSum >= target: // shrink while the window is still valid
best = min(best, right - left + 1)
windowSum -= arr[left]
left += 1
return best if best != infinity else 0The shape with a while-loop inside a for-loop looks like O(n²). But it never examines an element that it has already dropped. Each index enters the window exactly one time (when right reaches it). Each index leaves exactly one time (when left passes it). The total movement across both edges is a maximum of 2n steps.
| Operation | Time | Space | Why |
|---|---|---|---|
| Fixed-size window | O(n) | O(1) extra (plus the state that the window tracks) | One slide for each position. One element enters and one element leaves. Both are O(1). There are n slides in total. |
| Variable-size window | O(n) amortized | O(1) extra (plus the tracked state) | Remember "amortized" from Arrays & Strings Fundamentals. The inner while-loop looks like it can repeat. But left moves only forward and can advance a maximum of n times in the full run. So the two nested loops together are still O(n), not O(n²). |
| Recomputing every subarray from scratch (for comparison) | O(n²) or worse | O(1) | A new sum of a part of up to n elements, for each of up to n start points, is the cost. Sliding window exists to prevent this cost. |
Window larger than the array
A fixed-size window of width k assumes that at least k elements exist. If you build "the first window" with a sum of arr[0..k-1] and do not check the length first, you read past the end of the array. Always check k against the length of the array before you build the first window.
Recomputing the aggregate instead of updating it
It is easy to write code that looks like sliding window (a loop with a window of size k) but re-sums all k elements at each position. The correct method adds the element that enters and subtracts the element that leaves. The wrong method changes an O(n) sliding window into an O(n·k) brute force. The structure is the same, but there is no speed benefit.
Off-by-one on window boundary indices
The element that leaves a fixed-size window at position right is at right - k, not right - k + 1 or right - k - 1. The width of a window is right - left + 1, not right - left. Both are easy to get wrong. Both give a wrong answer with no error, not a crash.
A shrink condition that never triggers
If the shrink condition can never become false, left never advances and the window only grows. This changes a variable-size window into a full O(n) rescan at each step (O(n²) in total) instead of an amortized O(n) sweep. Trace the condition against a small example by hand before you trust it.
Sign in to mark problems done — progress syncs across devices.