Count subarrays for every array element in which they are the minimum | Java implementation of the above approach ; 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
import java . util . * ; public class gfg { static int [ ] countingSubarray ( int arr [ ] , int n ) { int a [ ] = new int [ n ] ; int nsml [ ] = new int [ n ] ; Arrays . fill ( nsml , - 1 ) ; int nsmr [ ] = new int [ n ] ; Arrays . fill ( nsmr , n ) ; Stack < Integer > st = new Stack < Integer > ( ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( st . size ( ) > 0 && arr [ ( int ) st . peek ( ) ] >= arr [ i ] ) st . pop ( ) ; nsmr [ i ] = ( st . size ( ) > 0 ) ? ( int ) st . peek ( ) : n ; st . push ( i ) ; } while ( st . size ( ) > 0 ) st . pop ( ) ; for ( int i = 0 ; i < n ; i ++ ) { while ( st . size ( ) > 0 && arr [ ( int ) st . peek ( ) ] >= arr [ i ] ) st . pop ( ) ; nsml [ i ] = ( st . size ( ) > 0 ) ? ( int ) st . peek ( ) : - 1 ; st . push ( i ) ; } for ( int i = 0 ; i < n ; i ++ ) { nsml [ i ] ++ ; nsmr [ i ] -- ; int r = nsmr [ i ] - i + 1 ; int l = i - nsml [ i ] + 1 ; a [ i ] = r * l ; } return a ; } public static void main ( String [ ] args ) { int N = 5 ; int arr [ ] = { 3 , 2 , 4 , 1 , 5 } ; int a [ ] = countingSubarray ( arr , N ) ; System . out . print ( " [ " ) ; int n = a . length - 1 ; for ( int i = 0 ; i < n ; i ++ ) System . out . print ( a [ i ] + " , ▁ " ) ; System . out . print ( a [ n ] + " ] " ) ; } }