Simple Java O(n) time O(n) space solution.


  • 6
    R

    Basically we iterate the array for two rounds. In first round we count how many citation in each bucket and in the second round we traverse back to find the maximum h.

    //O(n) solution O(n) space
    public int hIndex(int[] citations) {
        
        if(citations == null)   return 0;
        int[] buffer = new int[citations.length+1];
        Arrays.fill(buffer, 0);
        
        for(int num : citations) {
            int idx = Math.min(num, citations.length);
            buffer[idx]++;
        }
        
        int sum = 0;
        for(int i = buffer.length -1 ; i >= 0 ; i--) {
            sum += buffer[i];
            if(sum >= i) return i;
        }
        
        return 0;
    

    }


Log in to reply
 

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