Count Subarrays with Distinct Elements
MediumPractice library · +20 XPhash mapsliding windowtwo pointers
Given an array A of N integers and an integer K, find the number of subarrays that contain exactly K distinct elements.
Input
The first line contains two integers N and K. The second line contains N integers representing the array A.
Output
Print a single integer: the count of subarrays with exactly K distinct elements.
Constraints
1 <= N <= 200000, 1 <= K <= N, 0 <= A[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 2 1 2 1 3 4
Output
5
Subarrays with exactly 2 distinct elements are: [1,2], [2,1], [1,2,1], [2,1,3], [1,3], [3,4].
Example 2
Input
5 3 1 2 3 1 2
Output
6
Subarrays with exactly 3 distinct elements are: [1,2,3], [1,2,3,1], [2,3,1], [1,2,3,1,2], [2,3,1,2], [3,1,2].
Hints
Similar problems
- Longest Subarray with At Most K Distinct ElementsMedium
- Longest Subarray with Distinct ElementsHard
- Longest Substring With At Most K Distinct CharactersMedium
- Longest Segment with At Most K Distinct ElementsMedium
- Longest Subarray with Alternating ParityMedium
- Count Unique Element PairsMedium
More topics: Hash Map and Hashing problems, Two Pointers 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()
Example 1 input
5 2 1 2 1 3 4
Example 2 input
5 3 1 2 3 1 2