Sliding Window: Maximum Sum of k Consecutive Elements
One problem, three stages: make it work, make it fast, make it lean. Step through each stage in the visualizer, then run all three on a big input in the benchmark and watch the brute force overheat.
The real-world version
A monitoring dashboard shows the busiest 5-minute stretch of the day from per-second request counts: 86,400 numbers per server, recomputed for every server in the fleet.
The problem
Given an array of integers nums and a window size k, return the largest sum of any k consecutive elements.
nums = [2, 1, 5, 1, 3, 2, 9, 4], k = 3 → 15 # 2 + 9 + 4
Stage 1 · Smelt: Make it work
For every starting position, add up the next k elements from scratch and keep the best total.
def max_window_sum(nums, k):
best = float('-inf')
for start in range(len(nums) - k + 1):
total = 0
for i in range(start, start + k):
total += nums[i]
best = max(best, total)
return bestWhy it's not enough: Neighbouring windows share k − 1 elements, and this re-adds all of them every time.
Stage 2 · Hammer: Make it fast
Build a prefix-sum array once: prefix[i] is the sum of the first i elements. Any window's sum is then one subtraction: prefix[i + k] - prefix[i].
def max_window_sum(nums, k):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
return max(prefix[i + k] - prefix[i]
for i in range(len(nums) - k + 1))Why it's not enough: Linear time, but it stores a second array as long as the input.
Stage 3 · Polish: Make it lean
Keep one running total. Sliding the window right by one means adding the element that enters and subtracting the one that leaves: two operations, whatever the size of k.
def max_window_sum(nums, k):
total = sum(nums[:k])
best = total
for right in range(k, len(nums)):
total += nums[right] - nums[right - k] # in, out
best = max(best, total)
return bestWhy it holds up: Optimal: one pass, constant memory. This add-one, drop-one move is the whole sliding-window pattern.
X-ray: watch it run
Benchmark: will the forge overheat?
Run all three stages on a large input in your browser and compare the work each one does.
In the interview
Fixed-size windows like this one are the warm-up. The follow-up is usually a variable window ("longest substring without repeats"), where the left edge moves only when a rule breaks, and the same add/remove idea applies.
Go deeper: Sliding Window Technique