Smallest subarray with k distinct numbers | C ++ program to find minimum range that contains exactly k distinct numbers . ; prints the minimum range that contains exactly k distinct numbers . ; Initially left and right side is - 1 and - 1 , number of distinct elements are zero and range is n . ; Initialize right side ; increment right side . ; if number of distinct elements less than k . ; if distinct elements are equal to k and length is less than previous length . ; if number of distinct elements less than k , then break . ; if distinct elements equals to k then try to increment left side . ; increment left side . ; it is same as explained in above loop . ; Driver code for above function .
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minRange ( int arr [ ] , int n , int k ) { int l = 0 , r = n ; int j = -1 ; map < int , int > hm ; for ( int i = 0 ; i < n ; i ++ ) { while ( j < n ) { j ++ ; if ( hm . size ( ) < k ) hm [ arr [ j ] ] ++ ; if ( hm . size ( ) == k && ( ( r - l ) >= ( j - i ) ) ) { l = i ; r = j ; break ; } } if ( hm . size ( ) < k ) break ; while ( hm . size ( ) == k ) { if ( hm [ arr [ i ] ] == 1 ) hm . erase ( arr [ i ] ) ; else hm [ arr [ i ] ] -- ; i ++ ; if ( hm . size ( ) == k && ( r - l ) >= ( j - i ) ) { l = i ; r = j ; } } if ( hm [ arr [ i ] ] == 1 ) hm . erase ( arr [ i ] ) ; else hm [ arr [ i ] ] -- ; } if ( l == 0 && r == n ) cout << " Invalid ▁ k " << endl ; else cout << l << " ▁ " << r << endl ; } int main ( ) { int arr [ ] = { 1 , 1 , 2 , 2 , 3 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 3 ; minRange ( arr , n , k ) ; return 0 ; }