Count subarrays for every array element in which they are the minimum | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > countingSubarray ( vector < int > arr , int n ) { vector < int > a ( n ) ; vector < int > nsml ( n , -1 ) ; vector < int > nsmr ( n , n ) ; stack < int > st ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( ! st . empty ( ) && arr [ st . top ( ) ] >= arr [ i ] ) st . pop ( ) ; nsmr [ i ] = ( ! st . empty ( ) ) ? st . top ( ) : n ; st . push ( i ) ; } while ( ! st . empty ( ) ) st . pop ( ) ; for ( int i = 0 ; i < n ; i ++ ) { while ( ! st . empty ( ) && arr [ st . top ( ) ] >= arr [ i ] ) st . pop ( ) ; nsml [ i ] = ( ! st . empty ( ) ) ? st . top ( ) : -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 ; } int main ( ) { int N = 5 ; vector < int > arr = { 3 , 2 , 4 , 1 , 5 } ; auto a = countingSubarray ( arr , N ) ; cout << " [ " ; int n = a . size ( ) - 1 ; for ( int i = 0 ; i < n ; i ++ ) cout << a [ i ] << " , ▁ " ; cout << a [ n ] << " ] " ; return 0 ; }