Research impact from sorted citation counts
A researcher's citations are given in non-decreasing order: citations[i] is
the number of citations of their i-th paper. Their h-index is the largest h such that at
least h papers have at least h citations each. Return it, using O(log n) steps.
Examples
| Input | Output | Why |
|---|---|---|
citations = [0, 1, 3, 5, 6] | 3 | Three papers (3, 5, 6) have at least 3 citations; there are not four with at least 4. |
citations = [1, 2, 100] | 2 | |
citations = [0] | 0 |
Constraints
- 1 ≤ n ≤ 10⁵
- 0 ≤ citations[i] ≤ 1000
- citations is non-decreasing
Hints
Hint 1
Because the list is sorted, the papers from index i to the end are the n − i most cited. When do they all have at least n − i citations?
Hint 2
They do exactly when citations[i] ≥ n − i, since citations[i] is the smallest of them. Is that test monotone in i?
Hint 3
As i grows, citations[i] cannot fall and n − i falls, so once the test passes it keeps passing. Find the first i where it passes; the answer is n − i.
Where people lose marks
- Returning citations[i*] instead of n − i*. The h-index is a count of papers, not a citation number.
- Using a closed range and missing the case where no index passes (all zeros): the answer is then 0.
- Testing citations[i] > n − i: the definition says at least, so the comparison is ≥.
Dry run on [0,1,1,3,4,5,8,9,12]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6n9
Above each cell: its index and n − i, the number of papers from there to the end. Find the first i with citations[i] ≥ n − i.
-
Step 2 / 6lo0mid4hi9n − mid5
citations[4] = 4 < 5. The last 5 papers do not all reach 5: lo = 5.
-
Step 3 / 6lo5mid7hi9n − mid2
citations[7] = 9 ≥ 2. The last 2 papers all have at least 2 citations: hi = 7.
-
Step 4 / 6lo5mid6hi7n − mid3
citations[6] = 8 ≥ 3. The last 3 papers all have at least 3 citations: hi = 6.
-
Step 5 / 6lo5mid5hi6n − mid4
citations[5] = 5 ≥ 4. The last 4 papers all have at least 4 citations: hi = 5.
-
Step 6 / 6answer4
The first passing index is 5, so h = n − 5 = 4.
How to think about it
Fix an index i. The papers from i to the end are the n − i most cited,
and the least cited of them has citations[i]. So all n − i of them have at least
n − i citations exactly when
citations[i] ≥ n − i.
Moving i right can only raise the left side and lowers the right side, so the test is false for a
prefix of indices and true for the rest. Let i* be the first index where it is true (or
n if none). Then h = n − i*: the test at i* shows n − i* papers
with that many citations, and the failure at i* − 1 shows that n − i* + 1 papers is too
many to ask for.
This is the step from searching for a value to searching for a boundary: nothing in the array equals the answer, but a test built from the value and its position switches exactly once.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def h_index(citations):
n = len(citations)
lo, hi = 0, n # first i with citations[i] >= n - i, or n
while lo < hi:
mid = (lo + hi) // 2
if citations[mid] >= n - mid: # the last n - mid papers all have >= n - mid
hi = mid
else:
lo = mid + 1
return n - lo#include <vector>
int solve(const std::vector<int>& citations) {
const int n = (int)citations.size();
int lo = 0, hi = n; // first i with citations[i] >= n - i, or n
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (citations[mid] >= n - mid) hi = mid; else lo = mid + 1;
}
return n - lo;
}class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int lo = 0, hi = n; // first i with citations[i] >= n - i, or n
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (citations[mid] >= n - mid) hi = mid; else lo = mid + 1;
}
return n - lo;
}
}function hIndex(citations) {
const n = citations.length;
let lo = 0, hi = n; // first i with citations[i] >= n - i, or n
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (citations[mid] >= n - mid) hi = mid; else lo = mid + 1;
}
return n - lo;
}fn solve(citations: &[i64]) -> i64 {
let n = citations.len();
let (mut lo, mut hi) = (0usize, n); // first i with citations[i] >= n - i, or n
while lo < hi {
let mid = lo + (hi - lo) / 2;
if citations[mid] >= (n - mid) as i64 { hi = mid } else { lo = mid + 1 }
}
(n - lo) as i64
}import Data.Array
solve :: [Int] -> Int
solve citations = n - go 0 n
where
n = length citations
a = listArray (0, n - 1) citations
-- first i with a[i] >= n - i, or n
go lo hi
| lo >= hi = lo
| a ! mid >= n - mid = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- Unsorted citations: count papers by citation number (capped at n) and sweep from the top, O(n) with no sort.
- Citations arrive one at a time and the h-index must be reported after each: a min-heap of the top h counts.
Next problems
Where a value belongs in a sorted array
Return the first position whose element is at least the target: the lower bound, which answers both "is it here" and "where would it go".
Open the problem → Medium15 minFirst and last position of a value
Two lower-bound searches, one for "at least target" and one for "greater than target", give both ends of the run.
Open the problem → Medium20 minCount the partners that clear a threshold
Sort one list once; each query then becomes one lower-bound search for the smallest partner that is good enough.
Open the problem →Write a solution and run it against the real test table.
Keep going
Where a value belongs in a sorted array
Return the first position whose element is at least the target: the lower bound, which answers both "is it here" and "where would it go".
Open the problem → Medium15 minFirst and last position of a value
Two lower-bound searches, one for "at least target" and one for "greater than target", give both ends of the run.
Open the problem → Medium20 minCount the partners that clear a threshold
Sort one list once; each query then becomes one lower-bound search for the smallest partner that is good enough.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.