← All coding problems
Distinct Elements in Every Window
mediumPlacement Coding+20 XPTime limit 2s
For every window of k consecutive elements, count how many distinct values it contains. For [1, 2, 1, 3, 4, 2, 3] and k = 4 the answer is 3 4 4 3.
Input:
- line 1:
n k - line 2:
nintegers
Output: n − k + 1 numbers — the distinct count of each window, left to right.
Constraints: 1 ≤ k ≤ n ≤ 10⁵, 1 ≤ values ≤ 10⁹.
Think about it: keep a hash map of counts for the current window. Moving right adds one element and removes one; the number of distinct values is the number of keys with a count above zero.
Sample input 1
7 4 1 2 1 3 4 2 3
Sample output 1
3 4 4 3
Sample input 2
3 1 5 5 5
Sample output 2
1 1 1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).