Distinct Elements in Window

mediumSave

ArrayHash TableSliding Window

Given an array of integers and a number k, find the count of distinct numbers in every contiguous sub-array of size k. Return an array containing these counts.

Example 1

Input

Output

[3, 3, 2]

Explanation. Sub-arrays of size 4 are [1, 2, 1, 3], [2, 1, 3, 4], [1, 3, 4, 3]. Their counts of distinct integers are 3, 3, and 2, respectively.

Example 2

Input

Output

[1, 1, 1]

Explanation. All sub-arrays of size 2 contain the same number (1), so they all have a single distinct number.

Example 3

Input

[
  [],
  1
]

Output

[]

Explanation. An empty array results in no sub-arrays, therefore the result is an empty list of counts.

Example 4

Input

Output

[2, 1, 2, 2, 2, 2]

Explanation. Analyzing each window of size 3, the counts are uniquely deduced.

Follow-up: Can this problem be solved in O(n) time complexity? What data structure might be most effective for this purpose?

Constraints:

1. The array will contain at least one element and will not exceed 10,000 elements.\n2. The value of `k` will be a positive integer and will not be larger than the size of the input array.

Views: 4