H-Index II

Share

Given an array of citations sorted in ascending order, compute the researcher's h-index. The h-index is the largest h such that h papers have at least h citations each.

Example 1
Input: citations=[0,1,3,5,6] → Output: 3
Example 2
Input: citations=[1,2,100] → Output: 2

Solution Approach

Binary search on the h value. There are n-mid papers from index mid to n-1. h is valid if citations[mid] >= n-mid. Find the smallest mid where this holds.

  • lo=0, hi=n-1.
  • mid: if citations[mid] >= n-mid: hi=mid (valid h candidate, try smaller index).
  • Else: lo=mid+1.
  • Answer = n-lo.
Java
class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length, lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (citations[mid] >= n - mid) hi = mid - 1;
            else lo = mid + 1;
        }
        return n - lo;
    }
}
  • Time Complexity: O(log N)
  • Space Complexity: O(1)