Smallest subarray with all occurrences of a most frequent element | C ++ implementation to find smallest subarray with all occurrences of a most frequent element ; To store left most occurrence of elements ; To store counts of elements ; To store maximum frequency ; To store length and starting index of smallest result window ; First occurrence of an element , store the index ; increase the frequency of elements ; Find maximum repeated element and store its last occurrence and first occurrence ; length of subsegment ; select subsegment of smallest size ; Print the subsegment with all occurrences of a most frequent element ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void smallestSubsegment ( int a [ ] , int n ) { unordered_map < int , int > left ; unordered_map < int , int > count ; int mx = 0 ; int mn , strindex ; for ( int i = 0 ; i < n ; i ++ ) { int x = a [ i ] ; if ( count [ x ] == 0 ) { left [ x ] = i ; count [ x ] = 1 ; } else count [ x ] ++ ; if ( count [ x ] > mx ) { mx = count [ x ] ; mn = i - left [ x ] + 1 ; strindex = left [ x ] ; } else if ( count [ x ] == mx && i - left [ x ] + 1 < mn ) { mn = i - left [ x ] + 1 ; strindex = left [ x ] ; } } for ( int i = strindex ; i < strindex + mn ; i ++ ) cout << a [ i ] << " ▁ " ; } int main ( ) { int A [ ] = { 1 , 2 , 2 , 2 , 1 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; smallestSubsegment ( A , n ) ; return 0 ; }