public class HIndex {
    
    //Naive solution. O(nlogn) time
    public int hIndex0(int[] citations) {
        Arrays.sort(citations);
        int i = 1;
        for(; i <= citations.length && i <= citations[citations.length - i]; ++i);
        return i - 1;
    }
    
    //Linear solution.
    public int hIndex1(int[] citations) {
        int maxNum = 0;
        for (int citation : citations) {
            maxNum = Math.max(maxNum, citation);
        }
        int[] counts = new int[maxNum + 1];
        for (int citation : citations) {
            counts[citation]++;
        }
        int i = maxNum;
        for (; i >= 0; --i) {
            if (i < maxNum) {
                counts[i] += counts[i + 1];
            }
            if (counts[i] >= i) {
                break;
            }
        }
        return i;
    }
    
    //Improve the above solution to get the best O(n) solution.
    public int hIndex(int[] citations) {
        int[] counts = new int[citations.length + 1];
        for (int citation : citations) {
            if (citation >= citations.length) {
                counts[citations.length]++;
            } else {
                counts[citation]++;
            }
        }
        int countAbove = 0;
        for (int h = counts.length - 1; h >= 0; --h) {
            countAbove += counts[i];
            if (countAbove >= h) {
                return h;
            }
        }
        return 0;
    }
}