H-Index

H-Index is a small problem with a big lesson: a sort makes it easy, and a single observation — that no value larger than n can matter — lets you replace the sort with counting. That observation is the whole trick behind every linear-time sort in interviews.

It also shows the standard way to prove a greedy-looking scan correct: define the answer precisely, then show the scan stops exactly there.

The problem

A researcher's papers have citation counts. Their h-index is the largest number h such that at least h papers have at least h citations each. Given the list of citation counts, return the h-index.

• [6, 0, 3, 5, 1] → 3. Three papers (6, 5, 3) have at least 3 citations each. There are not four papers with at least 4.
• [10, 10, 10] → 3. h can never exceed the number of papers.

Constraints: 1 ≤ n ≤ 10⁵, and each count is between 0 and 10⁹.

Clarifying questions

• Can counts be 0? Yes; a paper with 0 citations never helps.
• Is the input sorted? No. (If it is sorted, the follow-up uses binary search.)
• Can h be 0? Yes, when every paper has 0 citations.
• Can counts be huge? Yes, up to 10⁹ — which rules out counting over the raw range.

Approach 1: the simple way

Try every h from n down to 1, and count the papers with at least h citations.

1def h_index_brute(citations: list[int]) -> int:2    """Try every h from the largest possible down."""3    for h in range(len(citations), 0, -1):4        if sum(1 for c in citations if c >= h) >= h:5            return h6    return 0

It is correct and O(n²) time: up to n values of h, each counting n papers. For n = 10⁵ that is 10¹⁰ steps. Each count re-reads every paper to answer a question — "how many papers have at least h?" — that an ordering would answer instantly.

The key insight

Sort the counts from largest to smallest. Now "how many papers have at least h citations?" is just "how far down the list do the counts stay at least h?"

Read the sorted list as a ranking. The paper at rank r (1-based) has the r-th highest count. If that count is at least r, then r papers each have at least r citations — so h is at least r. Walk down the ranks while the count at rank r is at least r; the last rank that passes is the answer. Once a count drops below its rank, every later count is even smaller and every later rank even larger, so nothing further can pass.

Then the second observation: h can never exceed n. A paper with 10⁹ citations counts exactly the same as a paper with n citations. So cap every count at n. Now the values live in the range 0 to n, and a counting sort handles that in O(n).

Approach 2: sort, then scan

1def h_index_sorted(citations: list[int]) -> int:2    """Sort descending; h is the number of papers whose citations beat their rank."""3    ranked = sorted(citations, reverse=True)4    h = 05    while h < len(ranked) and ranked[h] >= h + 1:   # paper h+1 has at least h+1 citations6        h += 17    return h

On [6, 0, 3, 5, 1] the ranked list is [6, 5, 3, 1, 0]. Rank 1 has 6 (at least 1), rank 2 has 5 (at least 2), rank 3 has 3 (at least 3), rank 4 has 1 (not at least 4): stop, h = 3.

This is O(n log n) time and O(n) space for the sorted copy. It is a perfectly good interview answer. The follow-up is "can you do it in linear time?"

Approach 3: optimised — counting sort with a cap

1def h_index(citations: list[int]) -> int:2    """Counting sort with every count above n capped at n: O(n)."""3    n = len(citations)4    papers = [0] * (n + 1)             # papers[c] = papers with exactly c citations (c capped at n)5    for c in citations:6        papers[min(c, n)] += 17    at_least = 0                       # papers with at least h citations8    for h in range(n, -1, -1):9        at_least += papers[h]10        if at_least >= h:11            return h12    return 0

1. Bucket each paper by its count, capped at n. Bucket n means "n or more".
2. Walk h from n down to 0, adding each bucket to a running total. After adding bucket h, at_least is the number of papers with at least h citations.
3. The first h (from the top) where at_least >= h is the largest valid h.

Dry run on [6, 0, 3, 5, 1], n = 5. The buckets are papers = [1, 1, 0, 1, 0, 2] — the 6 and the 5 both land in bucket 5.

Complexity: O(n) time — one pass to bucket, at most n + 1 steps to walk. O(n) space for the buckets. The cap is what makes it linear: without it the bucket array would need 10⁹ slots.

Edge cases

• All zeros, [0, 0]: buckets [2, 0, 0]; h = 2 and 1 fail; h = 0 passes: answer 0.
• One paper with many citations, [100]: capped into bucket 1; h = 1.
• Every count above n, [10, 10, 10]: all land in bucket 3; answer 3.
• Ties at the boundary, [4, 4, 0, 0]: two papers with at least 2, not three with at least 3: answer 2.

Follow-ups

• The counts are already sorted ascending? Binary search for the first index i where citations[i] >= n - i; the answer is n - i. O(log n).
• Papers arrive one at a time and you report h after each? Keep a min-heap of the papers that currently count; push each new paper, and pop while the smallest is below the heap's size.
• Where else does capping work? Any time the answer is bounded by n: Top K Frequent uses counts (at most n) as bucket indices; "first missing positive" ignores every value above n.