H-Index

Problem

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Solution

Brute Force Solution with Sorting

public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        Arrays.sort(citations);
        int len = citations.length;
        for (int h = len; h >= 0; h--) {
            int hPapers = 0, index = len - 1;
            while (index >= 0) {
                if (citations[index] >= h) hPapers++;
                else break;
                index--;
            }
            if (hPapers >= h) return h; //No need to check left papers with citations less than h, cause it's obvious
        }
        return 0;
    }
}

O(n) Solution using extra Array

public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        int len = citations.length;
        int[] counts = new int[len + 1]; //hIndex can be len at most
        for (int cite : citations) {
            if (cite < len) counts[cite]++;
            else counts[len]++;
        }
        int hPapers = 0;
        for (int h = len; h >= 0; h--) {
            hPapers += counts[h];
            if (hPapers >= h) return h;
        }
        return 0;
    }
}

Analysis

In the first solution, we sort the given citations and then we loop through every possible hIndex
Since hIndex can be len at most, we init hIndex = len then get hPapers using another while loop
For the while loop, we have a index from last to first to get counts of paper with hIndex citations
We return hIndex if our hPapers has counts at least hIndex

In the second solution, we have an array counts, counts[i] means the # of papers with i citations
For each citation from citations, we update counts[cite] and for cite > len, we add it to counts[len]
Then we count hPapers from highest hIndex = len
If we have at least hIndex numbers of hPapers, we return current hIndex
We don't need to check left papers because we starts from higher numbers of citations paper to lower numbers of citations paper