191. Distinct Values in Every Window
Core1000 ms256 MBSolved by 0%
For every window of k consecutive values, print how many DIFFERENT values it
contains.
For [1, 2, 1, 3, 4] with k = 3 the windows are 1 2 1 with 2 distinct, 2 1 3 with 3,
and 1 3 4 with 3.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000 ≤ value ≤ 1000000`
Input
The first line contains two integers n and k.
The second line contains n space-separated integers.
Output
Print n - k + 1 integers on ONE line, separated by single spaces, the distinct count for each window, left to right.
Input5 3
1 2 1 3 4
Output2 3 3
Noteis the worked example from the statement
Input1 1
7
Output1
Noteis a single value with a window of one
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.