Shortest subarray to be removed to make all Array elements unique | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( int a [ ] , int n , int k ) { map < int , int > m ; int extra = 0 ; for ( int i = k ; i < n ; i ++ ) m [ a [ i ] ] ++ ; for ( auto x : m ) extra += x . second - 1 ; if ( extra == 0 ) return true ; for ( int i = 1 ; i + k - 1 < n ; i ++ ) { if ( m [ a [ i + k - 1 ] ] > 1 ) extra -- ; m [ a [ i + k - 1 ] ] -- ; m [ a [ i - 1 ] ] ++ ; if ( m [ a [ i - 1 ] ] > 1 ) extra ++ ; if ( extra == 0 ) return true ; } return false ; } 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 ; } int main ( ) { int a [ 5 ] = { 1 , 2 , 1 , 2 , 3 } ; int n = sizeof ( a ) / sizeof ( int ) ; cout << minlength ( a , n ) ; }