DSA Sliding Window
A sliding window is a run of neighbouring values that moves across a list one step at a time. This lesson uses a fixed window, which keeps the same size at every step.
The first window
The first window covers the first k values. Its sum is built in full, once.
values = [2, 1, 5, 1, 3, 2]
k = 3
print(values[0:k])
print(sum(values[0:k]))One slide step
A slide drops the value that leaves and adds the value that enters. The window size stays at k.
values = [2, 1, 5, 1, 3, 2]
window_sum = 8
window_sum = window_sum - values[0] + values[3]
print(values[1:4])
print(window_sum)Every window from one slide rule
The same drop-and-add step produces each later sum. No window is summed from scratch.
values = [2, 1, 5, 1, 3, 2]
k = 3
sums = [sum(values[0:k])]
for i in range(k, len(values)):
sums.append(sums[-1] - values[i - k] + values[i])
print(sums)Example
values = [2, 1, 5, 1, 3, 2]
k = 3
window_sum = sum(values[0:k])
best = window_sum
updates = 0
print("first window sum:", window_sum)
for i in range(k, len(values)):
window_sum = window_sum - values[i - k] + values[i]
updates += 2
print("window sum after slide", i - k + 1, ":", window_sum)
if window_sum > best:
best = window_sum
print("maximum window sum:", best)
print("updates:", updates)Key points
- Sliding window: a run of neighbouring values that moves across a list
- The first window is summed in full, and every later window updates that sum
- Each slide costs one subtraction and one addition
- A fixed window holds exactly k values at every step
In this example, the first window of three days sums to 8. Each slide drops the leaving day and adds the entering day. The four window sums are 8, 7, 9 and 6, so the maximum is 9. Three slides cost six updates, however wide the window is.
Note
The window moves only forward, so each value enters once and leaves once
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
What is the maximum sum of any 2 consecutive values in [4, 1, 4]?