Count subarrays for every array element in which they are the minimum | C # program for the above approach ; Function to find the boundary of every element within which it is minimum ; Perform Binary Search ; Find mid m ; Update l ; Update r ; Inserting the index ; Function to required count subarrays ; Stores the indices of element ; Initialize the output array ; Left boundary , till the element is smallest ; Right boundary , till the element is smallest ; Calculate the number of subarrays based on its boundary ; Adding cnt to the ans ; Driver code ; Given array arr [ ] ; Function call
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static int binaryInsert ( ArrayList boundary , int i ) { int l = 0 ; int r = boundary . Count - 1 ; while ( l <= r ) { int m = ( l + r ) / 2 ; if ( ( int ) boundary [ m ] < i ) l = m + 1 ; else r = m - 1 ; } boundary . Insert ( l , i ) ; return l ; } static int [ ] countingSubarray ( int [ ] arr , int n ) { Dictionary < int , int > index = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) index [ arr [ i ] ] = i ; ArrayList boundary = new ArrayList ( ) ; boundary . Add ( - 1 ) ; boundary . Add ( n ) ; Array . Sort ( arr ) ; int [ ] ans = new int [ n ] ; foreach ( int num in arr ) { int i = binaryInsert ( boundary , index [ num ] ) ; int l = ( int ) boundary [ i ] - ( int ) boundary [ i - 1 ] - 1 ; int r = ( int ) boundary [ i + 1 ] - ( int ) boundary [ i ] - 1 ; int cnt = l + r + l * r + 1 ; ans [ index [ num ] ] += cnt ; } return ans ; } public static void Main ( string [ ] args ) { int N = 5 ; int [ ] arr = { 3 , 2 , 4 , 1 , 5 } ; int [ ] a = countingSubarray ( arr , N ) ; Console . Write ( " [ " ) ; int n = a . Length - 1 ; for ( int i = 0 ; i < n ; i ++ ) Console . Write ( a [ i ] + " , ▁ " ) ; Console . Write ( a [ n ] + " ] " ) ; } }