Count subarrays for every array element in which they are the minimum | Set 2 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minSubarray ( int * arr , int N ) { int result [ N ] ; stack < pair < int , int > > l , r ; for ( int i = 0 ; i < N ; i ++ ) { int count = 1 ; while ( ! l . empty ( ) && l . top ( ) . first > arr [ i ] ) { count += l . top ( ) . second ; l . pop ( ) ; } l . push ( { arr [ i ] , count } ) ; result [ i ] = count ; } for ( int i = N - 1 ; i >= 0 ; i -- ) { int count = 1 ; while ( ! r . empty ( ) && r . top ( ) . first >= arr [ i ] ) { count += r . top ( ) . second ; r . pop ( ) ; } r . push ( { arr [ i ] , count } ) ; result [ i ] *= count ; } for ( int i = 0 ; i < N ; i ++ ) { cout << result [ i ] << " ▁ " ; } } int main ( ) { int arr [ ] = { 3 , 2 , 1 , 4 } ; int N = sizeof ( arr ) / sizeof ( int ) ; minSubarray ( arr , N ) ; return 0 ; }