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 .
int max_val = 0 ; for ( int i = 0 ; i < n ; i ++ ) max_val = max ( max_val , arr [ i ] ) ; int freq [ max_val + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) freq [ arr [ i ] ] ++ ;