Intuition
Since the array is sorted ascending, if citations[mid] >= n - mid then all n-mid papers from mid onward have at least n-mid citations, giving an h-index of at least n-mid — so search left for an even larger h. Otherwise search right. The answer is n minus the final left boundary.
Explanation
Read the h-index off a sorted array
With citations sorted ascending and length n, consider index mid. There are exactly n - mid papers from mid to the end, each with >= citations[mid] citations. If citations[mid] >= n - mid, those n - mid papers each have at least n - mid citations, so the h-index is at least n - mid — we can try to do better by looking left. If citations[mid] < n - mid, this position can't support that h; go right.
l, r = 0, n-1
while l <= r:
mid = (l + r) // 2
if citations[mid] >= n - mid: r = mid - 1 # candidate, try larger h
else: l = mid + 1
return n - l
When the loop ends, l is the first index whose citations[l] >= n - l, and the h-index is n - l.
Worked example
citations = [0, 1, 3, 5, 6], n = 5.
l=0,r=4,mid=2:citations[2]=3 >= 5-2=3→ candidate,r=1.l=0,r=1,mid=0:citations[0]=0 >= 5-0=5? no →l=1.l=1,r=1,mid=1:citations[1]=1 >= 5-1=4? no →l=2.- loop ends,
l=2→ h-index= 5 - 2 = 3.
Three papers (3, 5, 6 citations) each cited at least 3 times → h-index 3.
Complexity
- Time: O(log n).
- Space: O(1).
Implementation
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (citations[mid] >= n - mid) r = mid - 1;
else l = mid + 1;
}
return n - l;
}
}