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
function countingSubarray ( arr , n ) { let a = new Array ( n ) ; let nsml = new Array ( n ) ; nsml . fill ( - 1 ) ; let nsmr = new Array ( n ) ; nsmr . fill ( n ) ; let st = [ ] ; for ( let i = n - 1 ; i >= 0 ; i -- ) { while ( st . length > 0 && arr [ st [ st . length - 1 ] ] >= arr [ i ] ) st . pop ( ) ; nsmr [ i ] = ( st . length > 0 ) ? st [ st . length - 1 ] : n ; st . push ( i ) ; } while ( st . length > 0 ) st . pop ( ) ; for ( let i = 0 ; i < n ; i ++ ) { while ( st . length > 0 && arr [ st [ st . length - 1 ] ] >= arr [ i ] ) st . pop ( ) ; nsml [ i ] = ( st . length > 0 ) ? st [ st . length - 1 ] : - 1 ; st . push ( i ) ; } for ( let i = 0 ; i < n ; i ++ ) { nsml [ i ] ++ ; nsmr [ i ] -- ; let r = nsmr [ i ] - i + 1 ; let l = i - nsml [ i ] + 1 ; a [ i ] = r * l ; } return a ; } let N = 5 ; let arr = [ 3 , 2 , 4 , 1 , 5 ] ; let a = countingSubarray ( arr , N ) ; document . write ( " " ) ; let n = a . length - 1 ; for ( let i = 0 ; i < n ; i ++ ) document . write ( a [ i ] + " " ) ; document . write ( a [ n ] + " " ) ;