Count subarrays for every array element in which they are the minimum | Set 2 | Java program for the above approach ; Function to count subarrays for each element where it is the minimum ; For the length of strictly larger numbers on the left of A [ i ] ; Storing x in result [ i ] ; For the length of strictly larger numbers on the right of A [ i ] ; Store x * y in result array ; Print the result ; Driver Code ; Function Call
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void minSubarray ( int [ ] arr , int N ) { int [ ] result = new int [ N ] ; Stack < pair > l = new Stack < > ( ) ; Stack < pair > r = new Stack < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { int count = 1 ; while ( ! l . isEmpty ( ) && l . peek ( ) . first > arr [ i ] ) { count += l . peek ( ) . second ; l . pop ( ) ; } l . add ( new pair ( arr [ i ] , count ) ) ; result [ i ] = count ; } for ( int i = N - 1 ; i >= 0 ; i -- ) { int count = 1 ; while ( ! r . isEmpty ( ) && r . peek ( ) . first >= arr [ i ] ) { count += r . peek ( ) . second ; r . pop ( ) ; } r . add ( new pair ( arr [ i ] , count ) ) ; result [ i ] *= count ; } for ( int i = 0 ; i < N ; i ++ ) { System . out . print ( result [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 2 , 1 , 4 } ; int N = arr . length ; minSubarray ( arr , N ) ; } }