# Java, O(n) time, with easy explanation.

• The idea is to see that the result can only range from 0 to the length of the array (because we can't have h-index greater than the total papers published). So we create an array "arr" which acts like a HashMap (using pigeon hole principle) and loop backwards from the highest element, then we find "tot" which is the total number of papers that has more than i citations, and we stop when tot>=i (total number of papers with more than i citations >= i). We don't need to keep going because we are trying the biggest i possible, we we stop and return the result.

``````public class Solution {
public int hIndex(int[] citations) {
int n = citations.length, tot=0;
int[] arr = new int[n+1];
for (int i=0; i<n; i++) {
if (citations[i]>=n) arr[n]++;
else arr[citations[i]]++;
}
for (int i=n; i>=0; i--) {
tot += arr[i];
if (tot>=i) return i;
}
return 0;
}
``````

}

• Brilliant solution! Could you talk more about the relation with pigeon hole principle? Thanks.

• Hi cfdream1, sorry for making misunderstanding, it has no relation with pigeon hole principle. I just made a HashMap using an array. @@

• thanks for the clarify

• can you explain why return i instead the total number of paper tot? isn't i the number of citation ? but h is the number of paper?

• Thanks for sharing. Clever.
The only concern is the "HashMap". It takes O(n) space.

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