Longest Subarray with At Most K Distinct Elements
Given an array of N integers and an integer K, find the length of the longest subarray that contains at most K distinct elements. If multiple such subarrays exist, return the length of the longest one. If no such subarray exists (e.g., K=0 and array is non-empty), return 0.
Input
The first line contains two integers N and K. The second line contains N integers A_1, A_2, ..., A_N.
Output
Print a single integer: the length of the longest subarray with at most K distinct elements.
Constraints
1 <= N <= 200000, 0 <= K <= N, 0 <= A_i <= 10^9.
Example 1
5 2 1 2 1 3 2
3
The longest subarray with at most 2 distinct elements is [1, 2, 1], length 3. Another is [1, 3, 2], length 3. The subarray [2, 1, 3, 2] has length 4 but contains 3 distinct elements (1, 2, 3).
Example 2
7 3 1 1 2 2 3 3 1
7
The entire array [1, 1, 2, 2, 3, 3, 1] has length 7 and contains 3 distinct elements (1, 2, 3).
Hints
Similar problems
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray with Distinct ElementsHard
- Longest Subarray with Sum at Most KMedium
- Distinct Elements in Sliding WindowMedium
- Longest Subarray with Equal HalvesMedium
- Distinct Elements in a Sliding WindowMedium
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()
5 2 1 2 1 3 2
7 3 1 1 2 2 3 3 1