compute the max value in the array and create frequency array of size max_val + 1. We can also use HashMap to store frequencies . We have used an array to keep remaining code simple .
$ max_val = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ max_val = max ( $ max_val , $ arr [ $ i ] ) ; $ freq = array_fill ( 0 , $ max_val + 1 , 0 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ freq [ $ arr [ $ i ] ] ++ ;