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


  • 54

    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;
    }
    

    }


  • 1
    C

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


  • 0

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


  • 0
    C

    thanks for the clarify


  • 0
    O

    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?


  • 0

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


Log in to reply
 

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