Count subarrays where second highest lie before highest | Python3 program to count number of distinct instance where second highest number lie before highest number in all subarrays . ; Finding the next greater element of the array . ; Finding the previous greater element of the array . ; Wrapper Function ; Finding previous largest element ; Finding next largest element ; Driver Code
from typing import List NEW_LINE MAXN = 100005 NEW_LINE def makeNext ( arr : List [ int ] , n : int , nextBig : List [ int ] ) -> None : NEW_LINE INDENT s = [ ] NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT nextBig [ i ] = i NEW_LINE while len ( s ) and s [ - 1 ] [ 0 ] < arr [ i ] : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT if len ( s ) : NEW_LINE INDENT nextBig [ i ] = s [ - 1 ] [ 1 ] NEW_LINE DEDENT s . append ( ( arr [ i ] , i ) ) NEW_LINE DEDENT DEDENT def makePrev ( arr : List [ int ] , n : int , prevBig : List [ int ] ) -> None : NEW_LINE INDENT s = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT prevBig [ i ] = - 1 NEW_LINE while ( len ( s ) and s [ - 1 ] [ 0 ] < arr [ i ] ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT if ( len ( s ) ) : NEW_LINE INDENT prevBig [ i ] = s [ - 1 ] [ 1 ] NEW_LINE DEDENT s . append ( ( arr [ i ] , i ) ) NEW_LINE DEDENT DEDENT def wrapper ( arr : List [ int ] , n : int ) -> int : NEW_LINE INDENT nextBig = [ 0 ] * MAXN NEW_LINE prevBig = [ 0 ] * MAXN NEW_LINE maxi = [ 0 ] * MAXN NEW_LINE ans = 0 NEW_LINE makePrev ( arr , n , prevBig ) NEW_LINE makeNext ( arr , n , nextBig ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( nextBig [ i ] != i ) : NEW_LINE INDENT maxi [ nextBig [ i ] - i ] = max ( maxi [ nextBig [ i ] - i ] , i - prevBig [ i ] ) NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT ans += maxi [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 3 , 2 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE print ( wrapper ( arr , n ) ) NEW_LINE DEDENT