Fixed-size sliding window

A window is a run of k neighbouring items. If a question asks about every such run, do not re-add k numbers each time. Slide: the new window is the old one plus the item entering, minus the item leaving.

window = sum(a[:k])                 # first window
for i in range(k, len(a)):
    window += a[i] - a[i - k]       # add the new, drop the old

The first window costs k steps; every slide after that costs 1. For 20,000 items and k = 10,000, that is about 30,000 steps instead of 100 million.

The same idea works for more than sums. To count distinct items in the window, keep a dict of counts: add the entering item, subtract the leaving one, and delete a key when its count hits 0.

Always check the edges: what if k is bigger than the list, and is your first window counted?

In the table, window changes by just two numbers per step.

See it run

temps = [3, 1, 4, 1, 5, 9]
k = 3
window = temps[0] + temps[1] + temps[2]
for i in range(3, 6):
    window += temps[i] - temps[i - k]

The first window is the first 3 temperatures. After that the window slides one step at a time.

Practice fixed-size sliding window

Exercise 1

A stall records sales for each day in sales. A "hot streak" is any run of k consecutive days whose total sales are at least goal. Write solution(sales, k, goal) to return how many hot streaks there are.

Rules:

Overlapping runs count separately (days 1-3 and days 2-4 are two different runs).
If k is larger than the number of days, there are no runs: return 0.
Sales are integers of 0 or more. Return an integer.

Constraints: 0 ≤ len(sales) ≤ 10^5; 1 ≤ k ≤ 10^5; 0 ≤ goal ≤ 10^9.

Example: solution([3, 1, 4, 1, 5, 9], 3, 8) returns 3: the runs total 8, 6, 10 and 15, and three of them are at least 8.

Exercise 2

A library logs the noise level every minute in noise. Write solution(noise, k) to find the quietest stretch: the run of k consecutive minutes with the smallest total noise. Return the index where that run starts.

Rules:

If several runs share the smallest total, return the earliest start.
Indexes start at 0. Noise levels are integers of 0 or more.

Constraints: 1 ≤ k ≤ len(noise) ≤ 10^5. Your solution must be fast on 10^5 minutes with a large k.

Example: solution([5, 1, 2, 8, 1, 1], 2) returns 4: the run totals are 6, 3, 10, 9, 2, and the smallest, 2, starts at index 4.

Exercise 3

A radio station logs the song id of every play in plays. Write solution(plays, k) to return the largest number of different songs found in any run of k consecutive plays.

Rules:

If there are fewer than k plays, use the whole list as the only run.
An empty plays gives 0.
Song ids are integers. Return an integer.

Constraints: 0 ≤ len(plays) ≤ 10^5; 1 ≤ k ≤ 10^5. Your solution must be fast on 10^5 plays with a large k.

Example: solution([1, 2, 1, 3, 3, 3], 3) returns 3: the runs hold 2, 3, 2 and 1 different songs, and the best is 3 (the run 2, 1, 3).

The explanation and tasks are public. Running this lesson requires an account with course access.

Practice

Loading Python…

Loading exercise content…

Visualizer Watch your code run line by line

Run your code, then choose Play to follow its execution.

Memory · names → values

Variables appear here as Python creates them.

Output & plots