H-Index

You are given a list of citation counts for a researcher's papers. The researcher's H-index is the largest number h such that the researcher has at least h papers with at least h citations each.

A sort-based solution works, but a counting approach can do it in O(n) time.

Why this is worth learning

The answer cannot exceed the number of papers. Therefore all citation counts above n are equivalent for deciding the answer and can share one bucket.

Before coding: one-minute experiment

For citations [100,0,2,2], what is the H-index, and why is it not 3?

Function signature

func HIndex(citations []int) int

Inputs / outputs

• citations: citation counts for each paper.
• Return: the H-index as an integer.

Example

citations = [3,0,6,1,5]
Output: 3

Reason: there are 3 papers with at least 3 citations.

Constraints

• 0 <= len(citations) <= 100_000
• 0 <= citations[i] <= 1_000_000_000

Core idea (near-solution)

The H-index is at most n (number of papers). You can count how many papers have each citation count, with all counts greater than n grouped into a single bucket.

Invariant: when scanning from n down to 0, maintain how many papers have at least that many citations.

Algorithm (step-by-step)

1. Let n = len(citations). Create buckets of size n+1.
2. For each c in citations:
   • If c >= n, increment buckets[n].
   • Else increment buckets[c].
3. Initialize count = 0.
4. For h from n down to 0:
   • Add buckets[h] to count.
   • If count >= h, return h.
5. Return 0.

Correctness sketch

Bucket min(c,n) records each paper exactly once. During the descending scan, count is the number of papers with at least h citations, because buckets for every larger citation threshold have already been accumulated. A threshold is feasible exactly when count>=h. The first feasible threshold encountered is the largest one: every larger threshold has already failed. Threshold zero is always feasible, ensuring termination even when there are no papers. Capping large citation values at n loses no relevant information because an H-index larger than n is impossible.

Trace (hand walkthrough)

Example input:
citations = [3,0,6,1,5]
Output: 3

Reason: there are 3 papers with at least 3 citations.

Walk:
- n=5; buckets at indices 0..5 are [1,1,0,1,0,2]
- citations 6 and 5 both enter bucket 5, because h cannot exceed n
- h=5: count=2 < 5, so fail
- h=4: count=2 < 4, so fail
- h=3: count=3 >= 3, so return 3 (the first feasible threshold)

Pitfalls to avoid

• Comparing h to the wrong count (must be papers with citations >= h).
• Forgetting that the maximum possible H-index is n.

Debugging lens

Test all zeros, all counts above n, and counts exactly equal to the proposed threshold. The condition is at least h papers, not exactly h papers.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• The bucket method avoids sorting and is stable for large inputs.

Reconstruction checkpoint

For citations [100,0,2,2], what is the H-index, and why is it not 3?

Return to Array & String · Module quiz