H-Index II
H-Index II is LeetCode 275 (Medium). You get an integer array citations, where citations[i] is how many times a researcher's i-th paper has been cited. The array is sorted in ascending order.
Return the researcher's h-index: the largest number h such that the researcher has at least h papers with h or more citations each.
- The only difference from H-Index (LeetCode 274) is that the input arrives sorted.
- Your algorithm must run in logarithmic time, so a single pass over the array is not enough.
- n == citations.length
- 1 <= n <= 10⁵
- 0 <= citations[i] <= 1000
- citations is sorted in ascending order.
Intuition
Because the array is sorted, one index tells you a lot. The n - i papers from index i to the end each have at least citations[i] citations, so index i proves an h-index of n - i exactly when citations[i] >= n - i.
As i moves right, citations[i] can only grow and n - i only shrinks. Once the test is true it stays true, so the indices split into a false block followed by a true block. Binary search finds that split in O(log n), and the first true index gives the most papers that clear the bar.
A sorted array, a logarithmic time limit, and a yes/no test whose answer flips once from no to yes: that is binary search on the boundary, not on a value. Write the test as a function of the index (citations[i] >= n - i), check that it is monotonic, and search for the first index where it holds. Koko Eating Bananas and First Bad Version use the same shape.
Approach
Before reading on: for citations = [0, 1, 3, 5, 6], write n - i under each value. Where does the citation count first reach that number? Then decide what your search should return when no index ever reaches it.
Turn the definition into a test on one index
With the array sorted, the n - i papers from index i onward all have at least citations[i] citations. So citations[i] >= n - i means "an h-index of n - i is achievable".
Check the test is monotonic
Moving right, citations rise and n - i falls, so once the test passes it passes for every later index. The indices form a false block and then a true block.
Binary search for the first passing index
Keep left = 0, right = n - 1. At each mid:
- if
citations[mid] >= n - mid,midpasses: the first pass is atmidor to its left, so setright = mid - 1; - otherwise it fails, and so does everything to its left: set
left = mid + 1.
When the loop ends, left is the first passing index, or n if none passes.
Return the paper count
The answer is n - left: the number of papers from the first passing index to the end. When left = n this is 0, so an array of zeros needs no special branch.
H-Index II solution in Python | C++ | Java
citations[i] citations, so a bar that reaches its step proves an h-index of n − i. Bars rise and steps fall, so once a bar reaches its step every later one does too. We search for the first.mid, so it is recomputed on every probe rather than fixed in advance.mid, so it is recomputed on every probe rather than fixed in advance.mid, so it is recomputed on every probe rather than fixed in advance.left = 2, the first bar that reaches its step. The papers from there to the end are the 3 that each have at least 3 citations, and no earlier index can do better. Found in 3 probes, not 5 checks.citations[i] citations, so a bar that reaches its step proves an h-index of n − i. Bars rise and steps fall, so once a bar reaches its step every later one does too. We search for the first.mid, so it is recomputed on every probe rather than fixed in advance.mid, so it is recomputed on every probe rather than fixed in advance.left = 1, the first bar that reaches its step. The papers from there to the end are the 2 that each have at least 2 citations, and no earlier index can do better. Found in 2 probes, not 3 checks.citations[i] citations, so a bar that reaches its step proves an h-index of n − i. Bars rise and steps fall, so once a bar reaches its step every later one does too. We search for the first.mid, so it is recomputed on every probe rather than fixed in advance.mid, so it is recomputed on every probe rather than fixed in advance.left ran one past the last index, to 3. Returning n − left gives 0 with no special case. A search whose left could not reach 3 would wrongly report 1 here.Common pitfalls
Returning the citation count instead of the paper count
return citations[left]
return n - left
The h-index counts papers. For [0, 4, 4, 4] the first passing index is 1, so three papers have at least 3 citations and the answer is 3, but citations[1] is 4. It also reads past the end when left = n.
Using > where the definition says at least
if citations[mid] > n - mid:
if citations[mid] >= n - mid:
"h papers with at least h citations" includes equality. On [1, 2, 100] the strict test rejects index 1 (2 papers, 2 citations) and returns 1 instead of 2.
Lower-bound template with right = n - 1
left, right = 0, n - 1
while left < right:
mid = (left + right) // 2
if citations[mid] >= n - mid:
right = mid
else:
left = mid + 1left, right = 0, n
while left < right:
... # same bodyIn the half-open template left can never move past right, so it cannot reach n, the "no index passes" result. For [0] it stops at 0 and returns 1 instead of 0. Start right at n, or use the closed left <= right loop above.
Edge cases
For [1, 2, 100] the paper with 100 citations still counts as one paper. The h-index can never exceed n, and the n - i side of the test caps it automatically: index 0 passing gives exactly n.
Complexity
H-Index vs H-Index II
The two problems have the same definition; only the input and the time limit differ, and that changes the algorithm.
| Problem | Input | Best method | Time |
|---|---|---|---|
| H-Index (LeetCode 274) | unsorted | count papers per citation value, capped at n, then scan down | O(n) |
| H-Index (LeetCode 274) | unsorted | sort, then scan for citations[i] >= n - i | O(n log n) |
| H-Index II (LeetCode 275) | sorted ascending | binary search for the first citations[i] >= n - i | O(log n) |
H-Index II FAQ
What is the h-index?
The largest h such that h of the papers have at least h citations each. A researcher with papers cited 6, 5, 3, 1 and 0 times has h-index 3: three papers have 3 or more citations, but there are not four papers with 4 or more.
Why is the comparison target n - mid and not a fixed value?
n - mid is the number of papers from mid to the end, and that is the h-value index mid would prove. It changes with mid, so the search looks for where two moving quantities cross rather than for a stored number. That moving target is what makes the H Index II LeetCode problem feel different from a plain binary search.
Can the answer be larger than the largest citation count?
No. If every paper has at most c citations, no set of more than c papers can each have more than c. And it can never be larger than n, the number of papers.