Count smaller elements present in the array for each array element | Java program for the above approach ; Function to count for each array element , the number of elements that are smaller than that element ; Stores the frequencies of array elements ; Traverse the array ; Update frequency of arr [ i ] ; Initialize sum with 0 ; Compute prefix sum of the array hash [ ] ; Traverse the array arr [ ] ; If current element is 0 ; Print the resultant count ; Driver Code
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static void smallerNumbers ( int arr [ ] , int N ) { int hash [ ] = new int [ 100000 ] ; for ( int i = 0 ; i < N ; i ++ ) hash [ arr [ i ] ] ++ ; int sum = 0 ; for ( int i = 1 ; i < 100000 ; i ++ ) { hash [ i ] += hash [ i - 1 ] ; } for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == 0 ) { System . out . println ( "0" ) ; continue ; } System . out . print ( hash [ arr [ i ] - 1 ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 4 , 1 , 1 , 2 } ; int N = arr . length ; smallerNumbers ( arr , N ) ; } }