Last Updated: 2 Aug, 2020
Smallest Subarray With K Distinct Elements
Easy
Asked in companies
Given an array 'A' consisting of 'N' integers, find the smallest subarray of 'A' containing exactly 'K' distinct integers.
Note :
If more than one such contiguous subarrays exist, consider the subarray having the smallest leftmost index.
For example - if A is [1, 2, 2, 3, 1, 3 ] and k = 2 then the subarrays: [1,2], [2,3], [3,1], [1,3] are the smallest subarrays containing 2 distinct elements. In this case, we will consider the starting and ending index of subarray [1,2] i.e. 0 and 1.
Input Format :
The first line contains two integers 'N' and 'K' denoting the total number of integers and number of distinct integers respectively.
The second line contains 'N' space-separated integers describing elements of the array 'A'.
Output Format :
Print two space-separated integers denoting the starting and ending index of the subarray if it exists, otherwise print -1.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Assume array starts with 0 index.
If more than one solution is possible then print the subarray with smaller left index.
Constraints :
1 <= N, K <= 10^6
-10^5 <= A[i] <= 10^5
Time limit: 1 sec
Approaches
Algorithm
- Pick each element from the array as the starting element(i) of the subarray,
- Initialize an empty set to store distinct elements in the subarray.
- Pick each remaining element(i, i+1,..n - 1) from the array as the last element(jth).
- Add the current element to the set.
- If the set size equals k then update the results and break from the inner loop(we have already found k distinct elements increasing the size of the subarray will either make more distinct elements or increase the subarray size with repeated elements which are not to be considered in the required results).
- If j == size of the array, it means we have not found any desired subarray starting from ith index and going forward we will be having fewer elements to consider. Break from the outer loop
- Print the output if found, otherwise, print “-1”.
Using the sliding window technique
Algorithm
- Initialize the map to store the count of each element.
- Initialize start and end to store the index of the required subarray.
- i, j denote the start and end of the window, i = 0, j = 0
- While the end < size of the array,
- In the map, increase the count of the end index's character by 1, if the character is not present in the map, increment the value of count.
- While the count of distinct elements equals K (i.e. the size of the map is equal to K)
- Find the length of subarray as j - i
- Compare it with the length of the minimum length you've found so far (initially 0)
- If the current length is less than the minimum, update the minimum length
- From the left side, i.e. i's side, decrease the count of ith character by 1. If it is already one, remove that character from the map
- Move i forward by 1
- If end is equal to n, that means no subarray was found with K distinct characters and we can print -1. Otherwise, we can print the start and end index we found.
Similar problems