Smallest subarray with k distinct numbers | Java 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
import java . util . * ; class GFG { static void minRange ( int arr [ ] , int n , int k ) { int l = 0 , r = n ; int j = - 1 ; HashMap < Integer , Integer > hm = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { while ( j < n ) { j ++ ; if ( j < n && hm . size ( ) < k ) hm . put ( arr [ j ] , hm . getOrDefault ( arr [ j ] , 0 ) + 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 . getOrDefault ( arr [ i ] , 0 ) == 1 ) hm . remove ( arr [ i ] ) ; else hm . put ( arr [ i ] , hm . getOrDefault ( arr [ i ] , 0 ) - 1 ) ; i ++ ; if ( hm . size ( ) == k && ( r - l ) >= ( j - i ) ) { l = i ; r = j ; } } if ( hm . getOrDefault ( arr [ i ] , 0 ) == 1 ) hm . remove ( arr [ i ] ) ; else hm . put ( arr [ i ] , hm . getOrDefault ( arr [ i ] , 0 ) - 1 ) ; } if ( l == 0 && r == n ) System . out . println ( " Invalid ▁ k " ) ; else System . out . println ( 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 ) ; } }