H-Index II
Given a sorted array citations where citations[i] is the number of citations the i-th paper received, return the researcher's h-index. The h-index is the maximum value h such that at least h papers have h or more citations.
Intuition
The array is already sorted in ascending order, so if you pick index i, there are n - i papers with citations[i] or more citations. You want the leftmost i where citations[i] >= n - i, because that means the remaining n - i papers all have at least n - i citations — and n - i is the h-index. Since citations[i] is non-decreasing and n - i is strictly decreasing, the predicate citations[i] >= n - i flips from false to true at exactly one point, which binary search finds in O(log n).
Any time you have a sorted array and a monotonic predicate that flips from false to true, binary search for the transition point is the tool. Here the predicate is citations[i] >= n - i. The h-index problem is a specific instance of this: one quantity increases, the other decreases, and you want where they cross.
Approach
Understand the h-index on a sorted array
For a sorted array of length n, the paper at index i has citations[i] citations, and there are n - i papers from index i to the end. The h-index is n - i at the leftmost i where citations[i] >= n - i. Beyond that index, citations only grows and n - i only shrinks, so the condition stays true — we want the first crossing.
Binary search for the leftmost valid index
Set left = 0 and right = n - 1. If citations[mid] >= n - mid, the answer could be at mid or earlier — set right = mid. Otherwise, set left = mid + 1. When the loop ends, left is the first index satisfying the condition, and the h-index is n - left.
Handle the case where no paper qualifies
If even the last paper has citations[n-1] < 1 (i.e., zero citations), no i satisfies the condition. After the loop, left == n, and the h-index is n - n = 0. Time is O(log n), space is O(1).
Solution
Common pitfalls
Returning citations[left] instead of n - left
return citations[left]
return n - left
The h-index is the count of papers with at least h citations — that count is n - left, not the citation value at that index. For [0, 1, 3, 5, 6] the answer is 3 (three papers with >= 3 citations), not 3 by coincidence or 5.
Using citations[mid] > n - mid (strict) instead of >=
if citations[mid] > n - mid:
right = midif citations[mid] >= n - mid:
right = midThe h-index definition includes equality: h papers with at least h citations. Using strict inequality misses the exact crossing point and can return an h-index that is one too low.
Not handling the empty result when left == n after the loop
return n - left # only works if left < n
return n - left
Actually, n - left when left == n correctly gives 0. The pitfall is adding a guard that returns -1 or raises an error for this case — there is no need; the formula handles it.
Edge cases
No index satisfies citations[i] >= n - i. left ends at n, h-index is 0.
ncitations[0] >= n, so left converges to 0, h-index is n.
If citations[0] >= 1, h-index is 1. If citations[0] == 0, h-index is 0.