Shortest subarray to be removed to make all Array elements unique | Java 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
import java . util . * ; import java . lang . * ; class GFG { static boolean check ( int a [ ] , int n , int k ) { Map < Integer , Integer > m = new HashMap < > ( ) ; int extra = 0 ; for ( int i = k ; i < n ; i ++ ) m . put ( a [ i ] , m . getOrDefault ( a [ i ] , 0 ) + 1 ) ; for ( Integer x : m . values ( ) ) extra += x - 1 ; if ( extra == 0 ) return true ; for ( int i = 1 ; i + k - 1 < n ; i ++ ) { if ( m . get ( a [ i + k - 1 ] ) > 1 ) extra -- ; m . put ( a [ i + k - 1 ] , m . get ( a [ i + k - 1 ] ) - 1 ) ; m . put ( a [ i - 1 ] , m . get ( a [ i - 1 ] ) + 1 ) ; if ( m . get ( a [ i - 1 ] ) > 1 ) extra ++ ; if ( extra == 0 ) return true ; } return false ; } static int minlength ( int a [ ] , int n ) { int lo = 0 , hi = n + 1 ; int ans = 0 ; while ( lo < hi ) { int mid = ( lo + hi ) / 2 ; if ( check ( a , n , mid ) ) { ans = mid ; hi = mid ; } else lo = mid + 1 ; } return ans ; } public static void main ( String [ ] args ) { int a [ ] = { 1 , 2 , 1 , 2 , 3 } ; int n = a . length ; System . out . println ( minlength ( a , n ) ) ; } }