Fixed-Size Windows
Maximum sum of any k consecutive items: don’t re-add k numbers each time — subtract the one leaving, add the one entering.
The problem
You're building a fitness app. A user has a list of calories burned each day, and they want to know their best 7-day streak — the run of 7 consecutive days where they burned the most in total. Simple enough: every window of 7 days is a candidate, and you want the biggest sum among them.
You could, for each starting day, add up the next seven values and remember the largest. With a year of data that's 358 windows times 7 additions — not slow, but obviously repetitive. Day 2 through day 8 shares six days with day 1 through day 7. You're re-summing numbers you already summed a moment ago.
A first attempt
The literal approach: a loop over every start, and an inner loop that re-sums k values.
def max_sum_k(arr, k):
best = None
for start in range(len(arr) - k + 1):
total = 0
for j in range(start, start + k): # re-sums k every window
total += arr[j]
best = total if best is None else max(best, total)
return bestfunction maxSumK(arr: number[], k: number): number {
let best = -Infinity;
for (let start = 0; start <= arr.length - k; start++) {
let total = 0;
for (let j = start; j < start + k; j++) total += arr[j]; // re-sums k
best = Math.max(best, total);
}
return best;
}int maxSumK(int[] arr, int k) {
int best = Integer.MIN_VALUE;
for (int start = 0; start <= arr.length - k; start++) {
int total = 0;
for (int j = start; j < start + k; j++) total += arr[j]; // re-sums k
best = Math.max(best, total);
}
return best;
}int maxSumK(int arr[], int n, int k) {
int best = INT_MIN;
for (int start = 0; start <= n - k; start++) {
int total = 0;
for (int j = start; j < start + k; j++) total += arr[j]; /* re-sums k */
if (total > best) best = total;
}
return best;
}int maxSumK(const vector<int>& arr, int k) {
int best = INT_MIN;
for (int start = 0; start + k <= (int)arr.size(); start++) {
int total = 0;
for (int j = start; j < start + k; j++) total += arr[j]; // re-sums k
best = max(best, total);
}
return best;
}Roughly n windows times k additions each: O(n · k). The overlap between consecutive
windows is the waste, and a fixed-size window removes it.
The insight
A fixed-size window never changes width — it's always exactly k wide. That makes the
bookkeeping wonderfully regular: both edges move together, one step at a time. When they
move, exactly one element enters on the right and exactly one leaves on the left.
So keep a running sum. To slide, add arr[right] and subtract arr[right - k]. The - k
offset is the whole trick: the element that leaves is always exactly k positions behind the
one that just entered.
Left edge = right edge − k
In a fixed window you don't need a separate left pointer at all. The element leaving is
arr[right - k], computed straight from the right edge. One pointer, one running sum.
How it works
Prime the first window
Add the first k elements once. This is the sum of window [0 .. k-1] and your first
candidate answer.
Advance the right edge
Move right from k to the end. At each position, add arr[right] — the element entering.
Drop the left edge
Subtract arr[right - k] — the element that just left the window. The running sum is now
exactly the sum of the current k-wide window.
Track the best
Compare against the best sum so far and keep the larger. Continue to the end.
Window of k = 4 over daily calories, edges marked [ ]:
index: 0 1 2 3 4 5
value: 300 500 200 400 600 100
[300 500 200 400] 600 100 sum = 1400
300 [500 200 400 600] 100 sum = 1400 - 300 + 600 = 1700 ← best
300 500 [200 400 600 100] sum = 1700 - 500 + 100 = 1300The code
def max_sum_k(arr, k):
window = sum(arr[:k]) # prime first window: O(k) once
best = window
for right in range(k, len(arr)):
window += arr[right] - arr[right - k] # enter right, leave right-k
best = max(best, window)
return bestfunction maxSumK(arr: number[], k: number): number {
let window = 0;
for (let i = 0; i < k; i++) window += arr[i]; // prime first window
let best = window;
for (let right = k; right < arr.length; right++) {
window += arr[right] - arr[right - k]; // enter right, leave right-k
best = Math.max(best, window);
}
return best;
}int maxSumK(int[] arr, int k) {
int window = 0;
for (int i = 0; i < k; i++) window += arr[i]; // prime first window
int best = window;
for (int right = k; right < arr.length; right++) {
window += arr[right] - arr[right - k]; // enter right, leave right-k
best = Math.max(best, window);
}
return best;
}int maxSumK(int arr[], int n, int k) {
int window = 0;
for (int i = 0; i < k; i++) window += arr[i]; /* prime first window */
int best = window;
for (int right = k; right < n; right++) {
window += arr[right] - arr[right - k]; /* enter right, leave right-k */
if (window > best) best = window;
}
return best;
}int maxSumK(const vector<int>& arr, int k) {
int window = 0;
for (int i = 0; i < k; i++) window += arr[i]; // prime first window
int best = window;
for (int right = k; right < (int)arr.size(); right++) {
window += arr[right] - arr[right - k]; // enter right, leave right-k
best = max(best, window);
}
return best;
}The same skeleton solves a whole family: swap the running sum for a running count, a maximum,
or an average, and you get "count of vowels in any window of k," "first negative in each
window," and so on.
Complexity
| Aspect | Cost | Why |
|---|---|---|
| Time | O(n) | prime once in O(k), then one O(1) update per slide |
| Space | O(1) | a single running sum plus the best-so-far |
When to use it
Fixed windows need a reversible aggregate
The slide works because a sum can be undone — subtract what leaves. That's true for sums, counts, and averages, but not for max or min: you can't "subtract" the element that was the maximum and instantly know the new one. For a rolling max or min over a fixed window, you need a monotonic deque instead of a running value.
Practice
Recap
- A fixed-size window is always exactly
kwide; both edges move together, so exactly one element enters and one leaves per step. - Keep one running aggregate and update it with
+= arr[right] - arr[right - k]— no second pointer needed — for anO(n)scan. - The pattern only works for reversible aggregates (sum, count, average); rolling max/min needs a monotonic deque.
How is this guide?
Last updated on