# Use Count Sort, Easy O(n) C++ Solution

• The time complexity of Count Sort is O(n+k), where k is the range of array.
The idea for count sort is to use a vector size of k to record frequency of of each number then travese the vector to make freq[i]= freq[i]+freq[i-1] then the freq[i]-1 will be the index of sorted array

In this question, we can know that our k is from 0 to n, where n is the length of array
For an array with each number > n then the H-index will be n
and for another array with each number =0 then the H-index will be 0

The algorithm will be 1 first use count sort and for citations[i]>=n we will record hash[n]++
2 then from the back of hash, hash[i]=hash[i]+hash[i+1]
3 find the first hash[i]>=i in hash, i is the H-index

``````int hIndex(vector<int>& citations) {
int len = citations.size();
vector<int> hash(len+1,0);
for(int i=0;i<len;i++)
{
if(citations[i]>=len) hash[len]++;
else hash[citations[i]]++;
}
for(int i=len-1;i>=0;i--)
{
hash[i]+=hash[i+1];
}
for(int i=len;i>=0;i--)
{
if(hash[i]>=i) return i;
}
return 0;
}``````

• Facebook phone interview has a very similar question.
Given一个unsorted array， find the greatest natural number N, such that, there exists at least N numbers in the array which are greater or equal to N
The idea is same

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.