Smallest subarray with 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
function minRange ( arr , n , k ) { let l = 0 , r = n ; let j = - 1 ; let hm = new Map ( ) ; for ( let i = 0 ; i < n ; i ++ ) { while ( j < n ) { j ++ ; if ( j < n && hm . size < k ) { if ( hm . has ( arr [ j ] ) ) hm . set ( arr [ j ] , hm . get ( arr [ j ] ) + 1 ) ; else hm . set ( arr [ j ] , 1 ) ; } if ( hm . size == k && ( ( r - l ) >= ( j - i ) ) ) { l = i ; r = j ; break ; } } if ( hm . size < k ) break ; while ( hm . size == k ) { if ( hm . has ( arr [ i ] ) && hm . get ( arr [ i ] ) == 1 ) hm . delete ( arr [ i ] ) ; else if ( hm . has ( arr [ i ] ) ) hm . set ( arr [ i ] , hm . get ( arr [ i ] ) - 1 ) ; i ++ ; if ( hm . size == k && ( r - l ) >= ( j - i ) ) { l = i ; r = j ; } } if ( hm . has ( arr [ i ] ) && hm . get ( arr [ i ] ) == 1 ) hm . delete ( arr [ i ] ) ; else if ( hm . has ( arr [ i ] ) ) hm . set ( arr [ i ] , hm . get ( arr [ i ] ) - 1 ) ; } if ( l == 0 && r == n ) document . write ( " " ) ; else document . write ( l + " " + r ) ; } let arr = [ 1 , 1 , 2 , 2 , 3 , 3 , 4 , 5 ] ; let n = arr . length ; let k = 3 ; minRange ( arr , n , k ) ;