Minimum common element in subarrays of all possible lengths | C ++ Program to implement the above approach ; Function to find maximum distance between every two element ; Stores index of last occurence of each array element ; Initialize temp [ ] with - 1 ; Traverse the array ; If array element has not occurred previously ; Update index in temp ; Otherwise ; Compare temp [ a [ i ] ] with distance from its previous occurence and store the maximum ; Compare temp [ i ] with distance of its last occurence from the end of the array and store the maximum ; Function to find the minimum common element in subarrays of all possible lengths ; Function call to find a the maximum distance between every pair of repetition ; Initialize ans [ ] to - 1 ; Check if subarray of length temp [ i ] contains i as one of the common elements ; Find the minimum of all common elements ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void max_distance ( int a [ ] , int temp [ ] , int n ) { map < int , int > mp ; for ( int i = 1 ; i <= n ; i ++ ) { temp [ i ] = -1 ; } for ( int i = 0 ; i < n ; i ++ ) { if ( mp . find ( a [ i ] ) == mp . end ( ) ) temp [ a [ i ] ] = i + 1 ; else temp [ a [ i ] ] = max ( temp [ a [ i ] ] , i - mp [ a [ i ] ] ) ; mp [ a [ i ] ] = i ; } for ( int i = 1 ; i <= n ; i ++ ) { if ( temp [ i ] != -1 ) temp [ i ] = max ( temp [ i ] , n - mp [ i ] ) ; } } void min_comm_ele ( int a [ ] , int ans [ ] , int temp [ ] , int n ) { max_distance ( a , temp , n ) ; for ( int i = 1 ; i <= n ; i ++ ) { ans [ i ] = -1 ; } for ( int i = 1 ; i <= n ; i ++ ) { if ( ans [ temp [ i ] ] == -1 ) ans [ temp [ i ] ] = i ; } for ( int i = 1 ; i <= n ; i ++ ) { if ( i > 1 && ans [ i - 1 ] != -1 ) { if ( ans [ i ] == -1 ) ans [ i ] = ans [ i - 1 ] ; else ans [ i ] = min ( ans [ i ] , ans [ i - 1 ] ) ; } cout << ans [ i ] << " ▁ " ; } } int main ( ) { int N = 6 ; int a [ ] = { 1 , 3 , 4 , 5 , 6 , 7 } ; int temp [ 100 ] , ans [ 100 ] ; min_comm_ele ( a , ans , temp , N ) ; return 0 ; }