Maximum product of indexes of next greater on left and right | Method to find the next greater value in left side ; Checking if current element is greater than top ; Pop the element till we can 't  get the larger value then  the current value ; Else push the element in the stack ; Method to find the next greater value in right ; Checking if current element is greater than top ; Pop the element till we can 't  get the larger value then  the current value ; Else push the element in the stack ; For each element storing the index of just greater element in left side ; For each element storing the index of just greater element in right side ; Finding the max index product ; Driver Code
def nextGreaterInLeft ( a ) : NEW_LINE INDENT left_index = [ 0 ] * len ( a ) NEW_LINE s = [ ] NEW_LINE for i in range ( len ( a ) ) : NEW_LINE INDENT while len ( s ) != 0 and a [ i ] >= a [ s [ - 1 ] ] : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT if len ( s ) != 0 : NEW_LINE INDENT left_index [ i ] = s [ - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT left_index [ i ] = 0 NEW_LINE DEDENT s . append ( i ) NEW_LINE DEDENT return left_index NEW_LINE DEDENT def nextGreaterInRight ( a ) : NEW_LINE INDENT right_index = [ 0 ] * len ( a ) NEW_LINE s = [ ] NEW_LINE for i in range ( len ( a ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT while len ( s ) != 0 and a [ i ] >= a [ s [ - 1 ] ] : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT if len ( s ) != 0 : NEW_LINE INDENT right_index [ i ] = s [ - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT right_index [ i ] = 0 NEW_LINE DEDENT s . append ( i ) NEW_LINE DEDENT return right_index NEW_LINE DEDENT def LRProduct ( arr ) : NEW_LINE INDENT left = nextGreaterInLeft ( arr ) NEW_LINE right = nextGreaterInRight ( arr ) NEW_LINE ans = - 1 NEW_LINE for i in range ( 1 , len ( left ) - 1 ) : NEW_LINE INDENT if left [ i ] == 0 or right [ i ] == 0 : NEW_LINE INDENT ans = max ( ans , 0 ) NEW_LINE DEDENT else : NEW_LINE INDENT temp = ( left [ i ] + 1 ) * ( right [ i ] + 1 ) NEW_LINE ans = max ( ans , temp ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT arr = [ 5 , 4 , 3 , 4 , 5 ] NEW_LINE print ( LRProduct ( arr ) ) NEW_LINE