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
using System ; using System . Collections . Generic ; class GFG { static void minRange ( int [ ] arr , int n , int k ) { int l = 0 , r = n ; int j = - 1 ; Dictionary < int , int > hm = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { while ( j < n ) { j ++ ; if ( j < n && hm . Count < k ) if ( hm . ContainsKey ( arr [ j ] ) ) hm [ arr [ j ] ] = hm [ arr [ j ] ] + 1 ; else hm . Add ( arr [ j ] , 1 ) ; if ( hm . Count == k && ( ( r - l ) >= ( j - i ) ) ) { l = i ; r = j ; break ; } } if ( hm . Count < k ) break ; while ( hm . Count == k ) { if ( hm . ContainsKey ( arr [ i ] ) && hm [ arr [ i ] ] == 1 ) hm . Remove ( arr [ i ] ) ; else { if ( hm . ContainsKey ( arr [ i ] ) ) hm [ arr [ i ] ] = hm [ arr [ i ] ] - 1 ; } i ++ ; if ( hm . Count == k && ( r - l ) >= ( j - i ) ) { l = i ; r = j ; } } if ( hm . ContainsKey ( arr [ i ] ) && hm [ arr [ i ] ] == 1 ) hm . Remove ( arr [ i ] ) ; else if ( hm . ContainsKey ( arr [ i ] ) ) hm [ arr [ i ] ] = hm [ arr [ i ] ] - 1 ; } if ( l == 0 && r == n ) Console . WriteLine ( " Invalid ▁ k " ) ; else Console . WriteLine ( l + " ▁ " + r ) ; } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 1 , 2 , 2 , 3 , 3 , 4 , 5 } ; int n = arr . Length ; int k = 3 ; minRange ( arr , n , k ) ; } }