Count subarrays for every array element in which they are the minimum | Function to required count subarrays ; For storing count of subarrays ; For finding next smaller element left to a element if there is no next smaller element left to it than taking - 1. ; For finding next smaller element right to a element if there is no next smaller element right to it than taking n . ; Taking exact boundaries in which arr [ i ] is minimum ; Similarly for right side ; Driver code ; Given array arr [ ] ; Function call
def countingSubarray ( arr , n ) : NEW_LINE INDENT a = [ 0 for i in range ( n ) ] NEW_LINE nsml = [ - 1 for i in range ( n ) ] NEW_LINE nsmr = [ n for i in range ( n ) ] NEW_LINE st = [ ] NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT while ( len ( st ) > 0 and arr [ st [ - 1 ] ] >= arr [ i ] ) : NEW_LINE INDENT del st [ - 1 ] NEW_LINE DEDENT if ( len ( st ) > 0 ) : NEW_LINE INDENT nsmr [ i ] = st [ - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT nsmr [ i ] = n NEW_LINE DEDENT st . append ( i ) NEW_LINE DEDENT while ( len ( st ) > 0 ) : NEW_LINE INDENT del st [ - 1 ] NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT while ( len ( st ) > 0 and arr [ st [ - 1 ] ] >= arr [ i ] ) : NEW_LINE INDENT del st [ - 1 ] NEW_LINE DEDENT if ( len ( st ) > 0 ) : NEW_LINE INDENT nsml [ i ] = st [ - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT nsml [ i ] = - 1 NEW_LINE DEDENT st . append ( i ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT nsml [ i ] += 1 NEW_LINE nsmr [ i ] -= 1 NEW_LINE r = nsmr [ i ] - i + 1 ; NEW_LINE l = i - nsml [ i ] + 1 ; NEW_LINE a [ i ] = r * l ; NEW_LINE DEDENT return a ; NEW_LINE DEDENT N = 5 NEW_LINE arr = [ 3 , 2 , 4 , 1 , 5 ] NEW_LINE a = countingSubarray ( arr , N ) NEW_LINE print ( a ) NEW_LINE