A map that slides
Report how many different values each window of k holds. About 9 minutes.
A set forgets too soon
A shop wants to know how many different products were sold in every 4-hour window of the day. Slide a window along the sales, as in Arrays. But when a product leaves the window, has it really gone? Only if no other sale of it is still inside.
A set can't tell you that: it knows whether a value is present, not how many copies. A map of counts can. A value has only truly left when its count drops to 0.
- answer
- [3]
- counts
- {1: 2, 2: 1, 3: 1}
First window: 1 appears twice, 2 and 3 once. 3 different values.
One answer per window
Fill the first window, record how many kinds it holds, then slide: one value in, one value out, updating their counts. After every slide, record the number of kinds again.
A list of n values has n − k + 1 windows, so that's how many answers you should end up with.
counts, answer = {}, []
for i, x in enumerate(nums):
counts[x] = counts.get(x, 0) + 1
if i >= k:
old = nums[i - k]
counts[old] -= 1
if counts[old] == 0:
del counts[old]
if i >= k - 1:
answer.append(len(counts))
return answerThe window 1, 2, 1 slides on to 2, 1, 3. The 1 at the front leaves. Is 1 still counted?
- AYes
- BNo
- CIt's counted twice now
Show the answer
Yes. Its count goes from 2 to 1: another 1 is still in the window.
Different values in each window
You get a list of numbers and a window size k (1 ≤ k ≤ n). For each run of k consecutive numbers, from left to right, return how many different values it contains.
nums = [1, 2, 1, 3, 4, 2, 3], k = 4 → [3, 4, 4, 3]
1 ≤ k ≤ n ≤ 100,000