Distinct Elements in Sliding Window
Given an array of N integers and an integer K, find the number of distinct elements in each contiguous subarray (window) of size K. The windows are formed by sliding a window of size K from the beginning to the end of the array. The first window is arr[0..K-1], the second is arr[1..K], and so on, until the last window arr[N-K..N-1].
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated integers representing the array elements.
Output
Print N-K+1 integers, separated by spaces, where each integer is the count of distinct elements in the corresponding window.
Constraints
1 <= K <= N <= 200000 -10^9 <= arr[i] <= 10^9
Example 1
8 3 1 2 1 3 4 2 3 1
2 3 3 3 3 3
Windows: [1,2,1]->2 distinct, [2,1,3]->3, [1,3,4]->3, [3,4,2]->3, [4,2,3]->3, [2,3,1]->3
Example 2
5 2 10 10 10 10 10
1 1 1 1
Windows: [10,10]->1 distinct, [10,10]->1, [10,10]->1, [10,10]->1
Hints
Similar problems
- Longest Substring Without RepeatsMedium
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray with At Most K Duplicate PairsMedium
- Longest Subarray With Sum XMedium
- Longest Segment with At Most K Distinct ElementsMedium
- Longest Substring With At Most K Distinct CharactersMedium
More topics: Hash Map and Hashing problems, Sliding Window problems, Stack 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 2 10 10 10 10 10