Shortest subarray to be removed to make all Array elements unique | 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
function check ( a , n , k ) { let m = new Map ( ) ; let extra = 0 ; for ( let i = k ; i < n ; i ++ ) m . set ( a [ i ] , m . get ( a [ i ] ) == null ? 1 : m . get ( a [ i ] ) + 1 ) ; for ( let x of m . values ( ) ) extra += x - 1 ; if ( extra == 0 ) return true ; for ( let i = 1 ; i + k - 1 < n ; i ++ ) { if ( m . get ( a [ i + k - 1 ] ) > 1 ) extra -- ; m . set ( a [ i + k - 1 ] , m . get ( a [ i + k - 1 ] ) - 1 ) ; m . set ( a [ i - 1 ] , m . get ( a [ i - 1 ] ) + 1 ) ; if ( m . get ( a [ i - 1 ] ) > 1 ) extra ++ ; if ( extra == 0 ) return true ; } return false ; } function minlength ( a , n ) { let lo = 0 , hi = n + 1 ; let ans = 0 ; while ( lo < hi ) { let mid = Math . floor ( ( lo + hi ) / 2 ) ; if ( check ( a , n , mid ) ) { ans = mid ; hi = mid ; } else lo = mid + 1 ; } return ans ; } let a = [ 1 , 2 , 1 , 2 , 3 ] ; let n = a . length ; document . write ( minlength ( a , n ) ) ;