H-Index II
Problem
citations is sorted in non-decreasing order. The h-index is the largest h such that at least h papers each have ≥ h citations. Compute it in O(log n).
citations = [0, 1, 3, 5, 6]3def hIndex(citations):
n = len(citations)
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if citations[mid] >= n - mid:
hi = mid - 1
else:
lo = mid + 1
return n - lofunction hIndex(citations) {
const n = citations.length;
let lo = 0, hi = n - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (citations[mid] >= n - mid) hi = mid - 1;
else lo = mid + 1;
}
return n - lo;
}class Solution {
public int hIndex(int[] citations) {
int n = citations.length, lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (citations[mid] >= n - mid) hi = mid - 1;
else lo = mid + 1;
}
return n - lo;
}
}class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(), lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (citations[mid] >= n - mid) hi = mid - 1;
else lo = mid + 1;
}
return n - lo;
}
};Explanation
The h-index is the largest h such that at least h papers have >= h citations. Since citations is already sorted, we can binary-search for the boundary instead of counting linearly.
Here is the key observation: for index i, there are exactly n - i papers from i to the end. So if citations[i] >= n - i, then those n - i papers all have at least n - i citations — a valid h of n - i. We want the smallest such i, because that makes n - i as large as possible.
The search shrinks hi = mid - 1 when citations[mid] >= n - mid (try for an even smaller index), and pushes lo = mid + 1 otherwise. When the loop ends, lo is that smallest qualifying index, and the answer is n - lo.
Example: citations = [0,1,3,5,6], n = 5. Index 2 has citations[2] = 3 and n - 2 = 3, so 3 >= 3 qualifies; index 1 fails (1 < 4). The smallest qualifying index is 2, giving h-index 5 - 2 = 3.
Binary search over the sorted array makes this O(log n), as the problem requires.