Skills101
← 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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.