Smallest subarray with k distinct numbers | Python3 program to find the 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 .
from collections import defaultdict NEW_LINE def minRange ( arr , n , k ) : NEW_LINE INDENT l , r = 0 , n NEW_LINE i = 0 NEW_LINE j = - 1 NEW_LINE hm = defaultdict ( lambda : 0 ) NEW_LINE while i < n : NEW_LINE INDENT while j < n : NEW_LINE INDENT j += 1 NEW_LINE if len ( hm ) < k and j < n : NEW_LINE INDENT hm [ arr [ j ] ] += 1 NEW_LINE DEDENT if len ( hm ) == k and ( ( r - l ) >= ( j - i ) ) : NEW_LINE INDENT l , r = i , j NEW_LINE break NEW_LINE DEDENT DEDENT if len ( hm ) < k : NEW_LINE INDENT break NEW_LINE DEDENT while len ( hm ) == k : NEW_LINE INDENT if hm [ arr [ i ] ] == 1 : NEW_LINE INDENT del ( hm [ arr [ i ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT hm [ arr [ i ] ] -= 1 NEW_LINE DEDENT i += 1 NEW_LINE if len ( hm ) == k and ( r - l ) >= ( j - i ) : NEW_LINE INDENT l , r = i , j NEW_LINE DEDENT DEDENT if hm [ arr [ i ] ] == 1 : NEW_LINE INDENT del ( hm [ arr [ i ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT hm [ arr [ i ] ] -= 1 NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if l == 0 and r == n : NEW_LINE INDENT print ( " Invalid ▁ k " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( l , r ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 1 , 2 , 2 , 3 , 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE k = 3 NEW_LINE minRange ( arr , n , k ) NEW_LINE DEDENT