I read editorial for this problem, and didn’t understand how to maintain the count array since the value max value could range upto 109 help me out with this.
You can use Coordinate Compression to map these values in the range(1…n).
Suppose the array is A={30,10,15,20}.
Sort the array A, B={10,15,20,30} (B is sorted array )
A[i] can be written as the index of first occurence of element A[i] in sorted array B.
(This can be found using binary Search)
A[1]=30 occurs at 4th position in B i.e A[1]=4
Similarly after mapping A becomes {4,1,2,3}.
Elements of array A are now mapped between 1 to n.