Sliding Window
A moving range.
Imagine a window that slides along an array, showing a few items at a time. As it moves one step, one item enters on the right, and one item leaves on the left. You don't need to recount everything. You just adjust. That's the sliding window technique.

- A window slides along
- One item in, one item out
- Adjust, don't recount
Best three day total
Here are daily sales, and we want the best total over any three days in a row. We add up the first three days. Then, for each step, we add the day entering the window, and subtract the day leaving it. Run it. The best three days total twenty one. Each step is O of one, so the whole scan is O of N, instead of re adding every window.
def best_window(sales, k):
window = sum(sales[:k])
best = window
for i in range(k, len(sales)):
window += sales[i] - sales[i - k]
best = max(best, window)
return best
sales = [4, 2, 7, 1, 8, 3, 10, 2]
print(best_window(sales, 3))21
Fixed and growing windows
Some windows have a fixed size, like three days. Others grow and shrink. The window grows on the right while things are fine, and shrinks from the left when a rule is broken. The next lesson uses that kind. Both are O of N, because each item enters and leaves the window at most once.
| key | value |
|---|---|
| Fixed window | size k, slide by one |
| Growing window | expand right |
| Shrinking | move left when needed |
| Cost | O(n), each item in and out once |
Summary
A sliding window adds what enters, and removes what leaves, so each step is O of one. Next, a famous growing window problem.
Key takeaways- Add the new item
- Remove the old item
- O(n)