Minimum common element in subarrays of all possible lengths | 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
def max_distance ( a , temp , n ) : NEW_LINE INDENT mp = { } NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT temp [ i ] = - 1 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( a [ i ] not in mp ) : NEW_LINE INDENT temp [ a [ i ] ] = i + 1 NEW_LINE DEDENT else : NEW_LINE INDENT temp [ a [ i ] ] = max ( temp [ a [ i ] ] , i - mp [ a [ i ] ] ) NEW_LINE DEDENT mp [ a [ i ] ] = i NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( temp [ i ] != - 1 ) : NEW_LINE INDENT temp [ i ] = max ( temp [ i ] , n - mp [ i ] ) NEW_LINE DEDENT DEDENT DEDENT def min_comm_ele ( a , ans , temp , n ) : NEW_LINE INDENT max_distance ( a , temp , n ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans [ i ] = - 1 NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( ans [ temp [ i ] ] == - 1 ) : NEW_LINE INDENT ans [ temp [ i ] ] = i NEW_LINE DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( i > 1 and ans [ i - 1 ] != - 1 ) : NEW_LINE INDENT if ( ans [ i ] == - 1 ) : NEW_LINE INDENT ans [ i ] = ans [ i - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT ans [ i ] = min ( ans [ i ] , ans [ i - 1 ] ) NEW_LINE DEDENT DEDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 6 NEW_LINE a = [ 1 , 3 , 4 , 5 , 6 , 7 ] NEW_LINE temp = [ 0 ] * 100 NEW_LINE ans = [ 0 ] * 100 NEW_LINE min_comm_ele ( a , ans , temp , N ) NEW_LINE DEDENT