Count smaller elements present in the array for each array element | 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
def smallerNumbers ( arr , N ) : NEW_LINE INDENT hash = [ 0 ] * 100000 NEW_LINE for i in range ( N ) : NEW_LINE INDENT hash [ arr [ i ] ] += 1 NEW_LINE DEDENT sum = 0 NEW_LINE for i in range ( 1 , 100000 ) : NEW_LINE INDENT hash [ i ] += hash [ i - 1 ] NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if ( arr [ i ] == 0 ) : NEW_LINE INDENT print ( "0" ) NEW_LINE continue NEW_LINE DEDENT print ( hash [ arr [ i ] - 1 ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 4 , 1 , 1 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE smallerNumbers ( arr , N ) NEW_LINE DEDENT