Smallest Subarray with K Distinct Elements Problem

Given an array A consisting of N integers, find the smallest subarray of A that contains exactly K distinct integers.

Input:

The first line contains two integers N and K, denoting the total number of integers and the number of distinct integers respectively. The second line contains N space-separated integers describing the elements of the array A.

Output:

Output two space-separated integers denoting the starting and ending indices of the subarray if it exists; otherwise, print -1.

Example:

Suppose A = [1, 2, 2, 3, 1, 3] and K = 2. The smallest subarrays with 2 distinct elements include [1,2], [2,3], [3,1], and [1,3]. The preferred subarray based on the smallest starting index is [1,2], which starts and ends at indices 0 and 1, respectively.

Constraints:

1

Question

Smallest Subarray with K Distinct Elements Problem

Given an array A consisting of N integers, find the smallest subarray of A that contains exactly K distinct integers.

Input:

The first line contains two integers N and K, denoting the total number of integers and the number of distinct integers respectively.
 The second line contains N space-separated integers describing the elements of the array A.

Output:

Output two space-separated integers denoting the starting and ending indices of the subarray if it exists; otherwise, print -1.

Example:

Suppose A = [1, 2, 2, 3, 1, 3] and K = 2. The smallest subarrays with 2 distinct elements include [1,2], [2,3], [3,1], and [1,3]. The preferred subarray based on the smallest starting index is [1,2], which starts and ends at indices 0 and 1, respectively.

Constraints:

1 <= N, K <= 10^6
-10^5 <= A[i] <= 10^5
Time limit: 1 sec

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function. Assume the array starts at index 0. If multiple solutions are possible, select the subarray with the smaller starting index.

Accepted Answer

Find the smallest subarray with exactly K distinct integers in an array.

Use a sliding window approach to keep track of the subarray with K distinct integers.
Use a hashmap to store the frequency of each integer in the current window.
Update the window size based on the number of distinct integers found.
Keep track of the smallest subarray meeting the criteria.
Return the starting and ending indices of the smallest subarray with K distinct integers.

Accepted Answer

simple make a window and keep on moving starting with i=0, j=0, keep increasing j until it is visited so yes a visited map is requried., and manage MaxAchieved till Now;

Asked in Uber