Distinct Elements in a Sliding Window
Given an array of N integers and an integer K, find the number of distinct elements in each contiguous subarray of size K. Print these counts in the order the subarrays appear.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers, the elements of the array.
Output
Print N-K+1 integers, the number of distinct elements in each subarray of size K.
Constraints
1 <= N <= 200000, 1 <= K <= N, The elements of the array are integers between -10^9 and 10^9.
Example 1
8 3 1 2 1 3 4 2 3 1
2 3 3 3 3 3
The subarrays of size 3 are [1,2,1] (2 distinct), [2,1,3] (3 distinct), [1,3,4] (3 distinct), [3,4,2] (3 distinct), [4,2,3] (3 distinct), [2,3,1] (3 distinct).
Example 2
5 5 10 20 20 10 30
3
There is only one subarray of size 5: [10, 20, 20, 10, 30], which has 3 distinct elements.
Hints
Similar problems
- Longest Subarray with At Most K Duplicate PairsMedium
- Group by ValueMedium
- Distinct Elements in Sliding WindowMedium
- Longest Segment with At Most K Distinct ElementsMedium
- Longest Subarray with Equal HalvesMedium
- Find the First Unique ElementMedium
More topics: Arrays problems, Hash Map and Hashing problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
8 3 1 2 1 3 4 2 3 1
5 5 10 20 20 10 30