Count subarrays for every array element in which they are the minimum | Java 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
import java . util . * ; class GFG { static int binaryInsert ( ArrayList < Integer > boundary , int i ) { int l = 0 ; int r = boundary . size ( ) - 1 ; while ( l <= r ) { int m = ( l + r ) / 2 ; if ( boundary . get ( m ) < i ) l = m + 1 ; else r = m - 1 ; } boundary . add ( l , i ) ; return l ; } static int [ ] countingSubarray ( int [ ] arr , int n ) { Map < Integer , Integer > index = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) index . put ( arr [ i ] , i ) ; ArrayList < Integer > boundary = new ArrayList < > ( ) ; boundary . add ( - 1 ) ; boundary . add ( n ) ; Arrays . sort ( arr ) ; int [ ] ans = new int [ n ] ; for ( int num : arr ) { int i = binaryInsert ( boundary , index . get ( num ) ) ; int l = boundary . get ( i ) - boundary . get ( i - 1 ) - 1 ; int r = boundary . get ( i + 1 ) - boundary . get ( i ) - 1 ; int cnt = l + r + l * r + 1 ; ans [ index . get ( 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 ) ; 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 ] + " ] " ) ; } }