in order to reach O(N) time ,we need to sort array in O(N) time.

In this problem, we can do that using counting sort.

However, counting sort requires extra O(N) space to do the trick, and as a result ,we will get the "count" for every element.

But in this problem, we only need the "count" information for element smaller than n

because h-index will be in range [0, n]

So we can get rid of elements bigger than n, then consider the array as a linkedlist and do the counting sort right on itself

Here is my implementation.

```
public int hIndex(int[] citations) {
int c=0, num=0;
for(int i=0;i<citations.length;i++){
c = citations[i];
if(c<0)continue;
//-1 means that the count of number is 0
//-2 means that the count of number is 1, and so forth
citations[i] = -1;
if(c<citations.length){
//loop like a linkedlist
while((num=citations[c])>-1){
citations[c] = -2;
if(num>citations.length-1){
break;
}
c = num;
}
if(num<citations.length){
citations[c]--;
}
}
}
c = 0;
for(int i=0;i<citations.length;i++){
num = -citations[i]-1; //occurrences of i
if(num>0){
if(i>=citations.length-(c+num-1)){
return i>=citations.length-c ? citations.length-c : i;
}
c += num;
}
}
return citations.length-c;
}
```