Sliding window
In short: A sliding window computes something for every consecutive range by adding the new element and removing the old one at each step: O(n) instead of O(n · k).
Problem
The revenue for the last 365 days
The shop's dashboard shows, for every day, the revenue for the last 365 days. The history is 10 years: 3650 days. The code computes every window from scratch: for each day it adds up the 365 days before it.
adds = 0
def recompute(sales, k): global adds sums = [] for start in range(len(sales) - k + 1): total = 0 for d in range(start, start + k): adds += 1 total += sales[d] sums.append(total) return sumssales = [(d * 37) % 101 * 10 + 500 for d in range(3650)]sums = recompute(sales, 365)print(f"Windows: {len(sums)}")print(f"Additions: {adds}")print(f"The best 365 days: €{max(sums)}")Windows: 3286Additions: 1199390The best 365 days: €3660503286 windows of 365 additions each: 1,199,390. That is n·k: with 1000 products, one chart each, it becomes 1.2 billion additions every night.
Yet two neighbouring windows differ in just two days. The other 364 are added up again and again.
The idea
Slide the window: +new day, −old day
The sum for days 2–8 is the sum for days 1–7, plus day 8, minus day 1. Day 8 comes into the window, day 1 goes out. The days in between are not touched.
So:
- the first window is added up once: k additions;
- every next one is the previous one + the new day − the oldest day: two operations, however large the window.
This is called a sliding window: a window of fixed length that moves by one element, while its result is updated from the previous one. Instead of (n − k + 1) · k operations there are k + 2(n − k). That is O(n), not O(n·k).
The window is two pointers moving in the same direction, as in the previous lesson: its start and its end. Here the distance between them is always k.
See it
The week slides
The sales for 12 days and the sum for every 7 consecutive days. The average for the week is the sum divided by 7.
def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) return sumssales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850]sums = slide(sales, 7)for d, total in enumerate(sums): print(f"Days {d + 1}–{d + 7}: €{total}")Days 1–7: €5430Days 2–8: €5500Days 3–9: €5470Days 4–10: €5540Days 5–11: €5560Days 6–12: €5830def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) return sumsStep by step, in words
- The first window: days 1–7. Its 7 days are added one by one: 7 additions, €5430.
- Day 8 comes in: +€890. Day 1 goes out: −€820. Days 2–8: €5500, with two operations instead of 7.
- Day 9 comes in: +€610. Day 2 goes out: −€640. Days 3–9: €5470, with two operations instead of 7.
- Day 10 comes in: +€980. Day 3 goes out: −€910. Days 4–10: €5540, with two operations instead of 7.
- Day 11 comes in: +€720. Day 4 goes out: −€700. Days 5–11: €5560, with two operations instead of 7.
- Day 12 comes in: +€850. Day 5 goes out: −€580. Days 6–12: €5830, with two operations instead of 7.
- 6 windows for 17 operations: 7 for the first and 2 for each next one. From scratch every time it would be 6 · 7 = 42.
total, not in sum: sum is a built-in function. The list of sums grows with append.Try it
Predict
The sales for five days and a window of 3 days. What does the program print?
def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) return sums
sales = [820, 640, 910, 700, 580]sums = slide(sales, 3)print(sums[-1])The first window is 820 + 640 + 910 = 2370. Then +700 −820 = 2250, then +580 −640 = 2190. The last sum is for days 3–5: 910 + 700 + 580 = 2190.
Try it
Fill in
Day i comes into the window. Which day goes out?
def slide(sales, k):
total = 0
for i in range(k):
total += sales[i]
sums = [total]
for i in range(k, len(sales)):
total += sales[i]
total -= sales[]
sums.append(total)
return sumsThe window that ends on day i runs from i - k + 1 to i. The previous one runs from i - k to i - 1. The difference is day i - k: it goes out.
Try it
Find the bug
The first sum is right, and after it the numbers jump up and down:
sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850]sums = slide(sales, 7)for d, total in enumerate(sums): print(f"Days {d + 1}–{d + 7}: €{total}")Days 1–7: €5430Days 2–8: €5560Days 3–9: €5280Days 4–10: €5650Days 5–11: €5390Days 6–12: €5520Pick the line with the bug.
The code subtracts yesterday, sales[i - 1], and not the day that leaves the window, sales[i - k]. Yesterday is still in the window. So every sum is wrong except the first: for days 2–8 it gives 5430 + 890 − 760 = 5560, while the right answer is 5500.
See it
Measure: from scratch against sliding
The same 10 years and a window of 365 days, and the function counts the additions and subtractions:
ops = 0
def slide(sales, k): global ops total = 0 for i in range(k): ops += 1 total += sales[i] sums = [total] for i in range(k, len(sales)): ops += 1 total += sales[i] ops += 1 total -= sales[i - k] sums.append(total) return sumssales = [(d * 37) % 101 * 10 + 500 for d in range(3650)]sums = slide(sales, 365)print(f"Windows: {len(sums)}")print(f"Operations: {ops}")print(f"The best 365 days: €{max(sums)}")Windows: 3286Operations: 6935The best 365 days: €3660506935 operations instead of 1,199,390, and the best 365 days are the same. Run both ways in the browser:
- Every window from scratch (K = 365)
O(n) - Sliding: +new −old
O(n)
| Algorithm | n = 1,000 | n = 3,650 | n = 10,000 | n = 100,000 |
|---|---|---|---|---|
| Every window from scratch (K = 365) | 232,140 | 1,199,390 | 3,517,140 | 36,367,140 |
| Sliding: +new −old | 1,635 | 6,935 | 19,635 | 199,635 |
def slide(sales, k): total = 0 for i in range(k): total += sales[i] sums = [total] for i in range(k, len(sales)): total += sales[i] total -= sales[i - k] sums.append(total) return sumsThe two curves are parallel: the window is always 365 days, so both grow with n. The difference is the factor. From scratch costs k per day, sliding costs 2 per day, however large the window. With a 30-day window sliding is 15 times faster, with 365 days about 180 times.
The idea
A window of variable length
Marketing asks: what is the longest period of consecutive days in which the advertising spend is €400 in total at most? Now the length of the window is not given. It is the answer.
The window has two edges, left and right:
rightmoves forward and adds a new day;- if the sum goes over the budget,
leftmoves forward and removes days on the left until the sum is within the budget again; - after that the window is allowed, and its length is a candidate for the longest.
def longest_within(spend, budget): best = 0 total = 0 left = 0 for right in range(len(spend)): total += spend[right] while total > budget: total -= spend[left] left += 1 best = max(best, right - left + 1) return bestspend = [120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60]print(f"Longest period within €400: {longest_within(spend, 400)} days")Longest period within €400: 5 daysThere is a loop inside a loop, but this is O(n), not O(n²). left never moves back: every day enters the window once and leaves it at most once. At most 2n moves in total.
This works because the spending is not negative: a longer window is never cheaper. If there are refunds (negative numbers), removing a day on the left may increase the sum, and the rule "shrink until it is within the budget" is no longer right.
See it
No repeated character: a window with a set
Another variable-length window: the longest piece of a log line in which no character repeats. Such pieces give away random tokens that should not be in the log. The window keeps its characters in a set. When the new character is already inside, left removes characters on the left until the repeat is gone:
def longest_unique(line): seen = set() best_start = 0 best_len = 0 left = 0 for right, c in enumerate(line): while c in seen: seen.remove(line[left]) left += 1 seen.add(c) if right - left + 1 > best_len: best_len = right - left + 1 best_start = left return line[best_start:best_start + best_len]line = "GET /cart?token=x9Kq2Lm7Pz&page=2"part = longest_unique(line)print(f"No repeated character: {part} ({len(part)})")No repeated character: ?token=x9Kq2Lm7Pz&pag (21)The check "is it there" in the set is O(1) on average, with a hash table. So here too the total is O(n).
for right, c in enumerate(line) gives both the position and the character.More precisely, if you are curious
What a "character" is. In Java, C# and JavaScript a string is made of 16-bit units (UTF-16). An emoji such as 🛒 is two such units, and the window will count them separately. In Python a string is made of code points, and 🛒 is one character. A log with Latin letters and digits is the same in all four languages.
The sum must not overflow. In Python integers have no upper limit, the sum does not overflow. In Java and C# int goes up to 2,147,483,647, and revenue in cents needs a long.
The sum must not drift. If the sales are in euros with cents in a double, every +new −old adds a tiny rounding error, and the errors pile up: after thousands of steps the window's sum is no longer exactly the sum of its days. Keep money in cents, as integers. If the numbers are floating point by nature (temperatures, times), compute the window from scratch every few thousand steps.
The average and the largest. The moving average is the sum divided by k. The largest value in the window does not work with +new −old: a maximum cannot be "subtracted". For it there is a sliding window with a double-ended queue (deque) that keeps the candidates for the maximum.
Exercise
The shortest period with revenue of at least €3500
Solve the task in your editor.
The shortest period. The sales for 12 days are €820, €640, €910, €700, €580, €1020, €760, €890, €610, €980, €720 and €850. What is the shortest period of consecutive days with revenue of at least €3500? The window grows to the right, and while the sum is at least €3500, remember its length if it is smaller, and shrink it from the left.
Shortest period with at least €3500: 5 days (from day 1 to day 5)More tasks
- The best week. With sliding, find which 7 consecutive days have the largest revenue and print them.
- A moving average. Print the average sales for every 7 days, rounded to the cent.
- Different customers per hour. The orders are sorted by minute, each with a customer number. For every 60-minute window, how many different customers are there? Keep in a map how many orders each customer has in the window.
Test