Fixed sliding window
easyConsecutive windows share k−1 elements, so recomputing from scratch is waste. Add the entering value, subtract the leaving one - O(1) per position.
O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How fixed sliding window works
The naive approach recomputes each window from scratch: k additions for every one of the n - k + 1 positions, roughly n·k work. Yet consecutive windows share k - 1 of their k elements. All that shared work is waste - the only real change from one window to the next is a single element entering and a single element leaving.
So keep a running sum. Pay k additions once for the first window, then slide: sum = sum + a[i] - a[i-k]. Two arithmetic operations per position, O(n) overall, O(1) memory. With k = 50 that is a 25x saving at every step - the trick costs nothing when k is small and pays proportionally as k grows.
The recognition line is every subarray of size k: maximum sum, minimum average, count above a threshold. Because k is fixed, both ends move in lockstep, which makes this the easy half of the sliding-window family. When the window must grow and shrink on a condition, you want the variable-size version instead.
Step by step
- Find the best 3-wide window in 4, 2, 9, 7, 1, 8. Build the first window: 4 + 2 + 9 = 15, so best = 15.
- Slide to positions 1..3: 7 enters, 4 leaves. sum = 15 + 7 - 4 = 18. A new best.
- Slide to 2..4: 1 enters, 2 leaves. sum = 18 + 1 - 2 = 17. best stays 18.
- Slide to 3..5: 8 enters, 9 leaves. sum = 17 + 8 - 9 = 16. Still short of 18.
- Answer: 18, the window 2, 9, 7 at positions 1..3. Each slide cost two operations where recomputation would have cost three.
- Total: the k = 3 build plus two operations per slide, nine in all - and that per-slide count stays two however large k gets.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(1) |
Reference implementation
Python
def max_window_sum(a, k):
"""Largest sum of any k consecutive elements, in O(n)."""
window = sum(a[:k])
best = window
for i in range(k, len(a)):
window += a[i] - a[i - k] # add the new, drop the old
best = max(best, window)
return bestJavaScript
function maxWindowSum(a, k) {
let window = 0;
for (let i = 0; i < k; i++) window += a[i];
let best = window;
for (let i = k; i < a.length; i++) {
window += a[i] - a[i - k]; // add the new, drop the old
best = Math.max(best, window);
}
return best;
}Worth noticing
Two arithmetic operations replace k additions
The naive version recomputes each window from scratch: n·k work. Sliding reuses the previous sum and adjusts by exactly the element entering and the element leaving - O(1) per position, so O(n) overall.
The overlap is the whole insight
Consecutive windows share k−1 elements. Any time consecutive subproblems overlap that heavily, recomputing from scratch is waste - the same observation that motivates prefix sums and dynamic programming.
Fixed windows are the easy half
Here k is given, so both ends move in lockstep. The harder and more common variant lets the window grow and shrink according to a condition - see the variable-size sliding window.
Common pitfalls
- Recomputing the sum inside the loop anyway. The code still passes tests - it is just O(n·k), which is precisely the cost the technique exists to remove.
- Getting the leaving index wrong: when a[i] enters, a[i-k] leaves. Writing a[i-k+1] or a[i-1] corrupts every sum after the first window.
- Not guarding k larger than n, which makes the first-window build read past the end before any sliding starts.
- Initialising best to 0 rather than the first window's sum - wrong the moment every window sums negative.
Where it is used
- Maximum or minimum sum over any k consecutive elements - the direct interview phrasing.
- Moving averages over time series and streams: the same two operations per new sample.
- Counting size-k subarrays that clear a threshold, since each window's sum arrives in O(1).
- Fixed-length pattern matching such as find-all-anagrams, sliding a frequency table instead of a sum.
Frequently asked questions
What are the time and space complexity of the fixed sliding window?
O(n) time: k additions build the first window, then every slide is one addition and one subtraction, regardless of k. Space is O(1) - the running sum and the best seen so far. The recompute-every-window baseline it replaces is O(n·k).
What is the difference between fixed and variable sliding windows?
Fixed: the size k is given, both ends advance together, one element in and one out per step. Variable: the window grows and shrinks to satisfy a condition, so the two ends move independently. Fixed is the strict special case, and the easier one to code.
Why not just use prefix sums for window sums?
Prefix sums answer the same window queries in O(1) each, but cost an O(n) build and O(n) extra memory. The running window needs neither. Prefix sums win when the ranges are arbitrary - different widths, random positions - rather than every consecutive window of one width.
Does the sliding trick work for maximum or minimum in a window?
Not by itself. A sum updates cleanly because the leaving element's contribution subtracts away. A maximum does not - when the maximum leaves, you must find the runner-up, which needs extra structure. The standard fix is a monotonic deque, which restores O(n) overall.