H-Index
Compute a researcher's h-index by sorting descending, or in linear time with counting
Problem Statement
Given an array citations where citations[i] is the number of citations received by the researcher's i-th paper, return their h-index.
The h-index is the maximum value h such that the researcher has published at least h papers that have each been cited at least h times.
Input: citations = [3, 0, 6, 1, 5]
Output: 3
Why: 3 papers (6, 5, 3) each have ≥ 3 citations.
There are not 4 papers with ≥ 4 citations, so h = 3.
Input: citations = [1, 3, 1]
Output: 1Intuition
The definition has two conditions locked together — at least h papers and each with at least h citations — which makes it hard to check in the original, unordered array.
The key insight
Sort descending. After sorting, "the top h papers" is simply the first h entries, and the weakest of them is citations[h-1]. So the whole condition collapses to a single comparison per position:
citations[i] >= i + 1
Read it as: "the paper at 0-based index i is the (i+1)-th best, and it has at least i + 1 citations — so h = i + 1 is achievable."
Because the array is sorted descending, once this test fails it fails for every larger i — citations only go down while the required count goes up. The answer is the last i + 1 for which the test passed.
Watch it run
Approach
Scan left to right
At index i, check citations[i] >= i + 1.
Stop at the first failure
The count of positions that passed is the h-index. Returning i at the first failure gives exactly that count.
If every position passes
Then h = n — every paper has at least n citations.
Solution
def h_index(citations: list[int]) -> int:
"""Maximum h such that h papers each have at least h citations."""
citations.sort(reverse=True)
for i, count in enumerate(citations):
if count < i + 1:
return i # i papers qualified before this one failed
return len(citations) # every paper qualifiedThe linear-time version
Sorting costs O(n log n), but there is a bound worth exploiting.
The h-index can never exceed the number of papers
You cannot have 10 papers with ≥ 10 citations if you only published 5. So h ≤ n, and any citation count above n may as well be treated as exactly n — the extra citations cannot raise h.
That bounds the interesting range to 0 … n, which means counting sort applies.
def h_index_counting(citations: list[int]) -> int:
"""O(n) time using counting sort over the bounded range 0..n."""
n = len(citations)
buckets = [0] * (n + 1)
for count in citations:
buckets[min(count, n)] += 1 # anything above n is capped at n
papers = 0
for h in range(n, -1, -1):
papers += buckets[h] # papers with at least h citations
if papers >= h:
return h
return 0Walking h downward accumulates papers with at least h citations. The first h where that running total reaches h is the answer, since larger values of h were already rejected.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(1)
- Sorting version —
O(n log n)time dominated by the sort,O(1)extra space (it sorts in place). - Counting version —
O(n)time andO(n)space for the buckets. The classic trade.
Edge Cases
Related Problems
- Sort the People — sorting to reveal an otherwise hidden order
- Top K Frequent Elements — the same "bounded values become array indices" trick
- Binary Search — H-Index II solves the pre-sorted variant in
O(log n)