Shortest subarray to be removed to make all Array elements unique | Python3 program to make array elements pairwise distinct by removing at most one subarray of minimum length ; Function to check if elements of Prefix and suffix of each sub array of size K are pairwise distinct or not ; Hash map to store frequencies of elements of prefix and suffix ; Variable to store number of occurrences of an element other than one ; Adding frequency of elements of suffix to hash for subarray starting from first index There is no prefix for this sub array ; Counting extra elements in current Hash map ; If there are no extra elements return true ; Check for remaining sub arrays ; First element of suffix is now part of subarray which is being removed so , check for extra elements ; Decrement frequency of first element of the suffix ; Increment frequency of last element of the prefix ; Check for extra elements ; If there are no extra elements return true ; Function for calculating minimum length of the subarray , which on removing make all elements pairwise distinct ; Possible range of length of subarray ; Binary search to find minimum ans ; Driver code
from collections import defaultdict NEW_LINE def check ( a , n , k ) : NEW_LINE INDENT m = defaultdict ( int ) NEW_LINE extra = 0 NEW_LINE for i in range ( k , n ) : NEW_LINE INDENT m [ a [ i ] ] += 1 NEW_LINE DEDENT for x in m : NEW_LINE INDENT extra += m [ x ] - 1 NEW_LINE DEDENT if ( extra == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( 1 , i + k - 1 < n ) : NEW_LINE INDENT if ( m [ a [ i + k - 1 ] ] > 1 ) : NEW_LINE INDENT extra -= 1 NEW_LINE DEDENT m [ a [ i + k - 1 ] ] -= 1 NEW_LINE m [ a [ i - 1 ] ] += 1 NEW_LINE if ( m [ a [ i - 1 ] ] > 1 ) : NEW_LINE INDENT extra += 1 NEW_LINE DEDENT if ( extra == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def minlength ( a , n ) : NEW_LINE INDENT lo = 0 NEW_LINE hi = n + 1 NEW_LINE ans = 0 NEW_LINE while ( lo < hi ) : NEW_LINE INDENT mid = ( lo + hi ) // 2 NEW_LINE if ( check ( a , n , mid ) ) : NEW_LINE INDENT ans = mid NEW_LINE hi = mid NEW_LINE DEDENT else : NEW_LINE INDENT lo = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 2 , 1 , 2 , 3 ] NEW_LINE n = len ( a ) NEW_LINE print ( minlength ( a , n ) ) NEW_LINE DEDENT