Loading...
Loading...
Loading...
A shop lists n sales in order, each as a product id. For every window of k consecutive sales, print how many different products it contains. Rebuilding a set for every window is too slow when k is large.
Example
Input
7 4 1 2 1 3 4 2 3
Output
3 4 4 3
Try the problem first. Open one hint at a time.
len(set(window)) for every window costs O(n × k).
Keep a Counter for the current window. When it slides, add the new id and subtract the id that left; delete a key whose count reaches zero.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor