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.

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

• Invariant: when scanning from n down to 0, maintain how many papers have at least that many citations.
• Frequency counts reflect the exact multiplicity of each value.
• The decision rule derived from counts is applied once, so no case is missed.
• Therefore the computed result matches the definition of the problem.

Trace (hand walkthrough)

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

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

Walk:
- sort desc: [6,5,3,1,0]
- i=0: 6>=1 -> h=1
- i=1: 5>=2 -> h=2
- i=2: 3>=3 -> h=3
- i=3: 1<4 -> stop => h=3

Pitfalls to avoid

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

Complexity

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

Implementation notes (Go)

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