Smallest subarray with k distinct numbers

We are given an array consisting of n integers and an integer k. We need to find the minimum range in array [l, r] (both l and r are inclusive) such that there are exactly k different numbers. If such subarray doesn’t exist print “Invalid k”.
Examples: 

Input : arr[] = { 1, 1, 2, 2, 3, 3, 4, 5} 
            k = 3
Output : 5 7

Input : arr[] = { 1, 2, 2, 3} 
            k = 2
Output : 0 1

Input : arr[] = {1, 1, 2, 1, 2}
            k = 3
Output : Invalid k

Approach 1 : (Brute Force Method)

The simplest approach in this problem is, try to generate all the subarrays and check for which subarray the size is k. But there are some points we need to take care.

Steps:

1. Pick each of the elements from the given array as the starting element [ i-th element ] of our required subarray.
2. In each iteration initialize an empty set to store the distinct elements of the subarray
   • Pick each remaining element [ i, i+1,..n – 1] from the array as the last element [ j-th element ].
   • Add the current element to the set.
   • If the set size equals k then update the results and break from the inner loop (already found k distinct elements increasing the size of the subarray has 2 possibilities either will get more distinct elements, or increase the subarray size with repeated elements which are not to be considered in the required results).
3. If (j == n) or j = size of the array, i.e. we have not found any desired subarray starting from i-th index and going forward we will be having fewer elements to consider.
   ( For example : consider given array is 4 5 5 4 5  and k = 3, when start from 0th index we will not find any subarray of k size and j will reach end so that means we won’t get any element that can make a k = 3 size required subarray). 
   So, Break from the outer loop.
4. Print the output if found, otherwise, print “Invalid k”.

Implementation:

0 2

Time Complexity : O(N^2) ,where N is the number of elements in the array. Every time picking the end points of the subarray using two nested loops(one inside another) makes the time complexity O(N^2).
Space Complexity :  O(N), In the worst case, we can have all ‘N’ elements in our set.

Approach 2 : (Sliding Window Approach)

Optimization is get rid of the repeated work while making all subarray, all subarray will not help to find the resultant. The approach is –

Steps :

• Initialize a map to store the frequencies of each element.
• Taking two variables as taken before : start and end of the required subarray.
• And here we are using i and j as the starting and ending index of the window respectively, initializing as i = 0 and j = 0.
• Will traverse the array while the ending pointer of our window reach the end of given array. i.e.  while( j < n)
  1. Add the current element to the map map[ arr[j] ]++ and make j pointing to the next index
  2. Consider the window [ i, j-1 ] (reason for ‘j-1’ is as we incremented the value of ‘j’ just after insertion in last step) check whether its size is equal to k
  3. If window size is lesser than k then continue
  4. But if window size == k, then check its length whether it is the resultant subarray or not. 
  5. After that we need to move our window, but in order to move our window, we have to check the starting element of our current window (i.e. i-th). If the i-th element is having a frequency of 1 then erase it from the map and else decrease its frequency by 1. And increase the i-value. Make i to point to the next element.

( For understanding the reason of erase and decreasing frequency, take an example :  4 2 2 3 4 4 3 and k = 3  when we are dealing with the window 2 2 3 4 then ‘i’ would have pointed to the start of window (first 2) and ‘j’ would have pointed to the last of window (at 4). Now while moving forward (by one position), if the window totally erase 2 from the map, (and make window 2 3 4 4) then map would contain the information that 2 is not in the map but it is wrong so we will decrease the count of 2. Similarly, in case of having frequency == 1, and about to leave the window, the map should not contain the frequency of the element which not there in the window. )

Implementation:

5 7

Time Complexity : O(N) ,where N is the number of elements in the array. In the worst case, each element will be added once and removed once from the map.
Space Complexity :  O(K), In the worst case, we can have only ‘K’ elements in our map.

GeeksforGeeks

Improve