H-Index

Problem

You are given an array citations where citations[i] is the number of citations a researcher’s i-th paper received. Compute the researcher’s h-index: the largest number h such that the researcher has at least h papers with at least h citations each.

Equivalently: find the largest h for which “h papers each have h or more citations” holds. h can never exceed the number of papers.

Examples

Example 1: citations = [3,0,6,1,5] → 3 Three papers (with 3, 6, 5 citations) each have ≥ 3 citations. There are not four papers with ≥ 4 citations each (only 6 and 5 qualify), so h = 3.

Example 2: citations = [1,3,1] → 1 Only one paper has ≥ 2 citations, so h = 2 fails. All three papers have ≥ 1 citation, so h = 1 holds.

Example 3: citations = [100] → 1 With a single paper, h cannot exceed 1.

Constraints

• n == citations.length, 1 <= n <= 5000
• 0 <= citations[i] <= 1000

n ≤ 5000 lets an O(n²) scan pass, but the intended answers are O(n log n) via sorting or O(n) via counting — and the O(n) one exploits that h can never exceed n.

Think about it first

TL;DR

Counting (bucket) sweep capped at n — O(n) time, O(n) space (sorting variant: O(n log n) time, O(1)–O(n) space).

Approach 1 — Brute force (test every h)

The h-index ranges over 0..n. For each candidate h, count how many papers have ≥ h citations and keep the largest h that works. Scanning from n downward returns the first (largest) h that satisfies the condition.

from typing import List


def hIndex(citations: List[int]) -> int:
    n = len(citations)
    for h in range(n, -1, -1):
        if sum(1 for c in citations if c >= h) >= h:
            return h
    return 0

Complexity: O(n²) time, O(1) space. At n = 5000 that is about 2.5·10^7 comparisons, which passes here, but it makes n passes over the array where the later approaches make one.

Approach 2 — Sort descending, scan

Sort citations from high to low. At 0-based index i, exactly i + 1 papers have at least citations[i] citations. So while citations[i] >= i + 1 holds, an h-index of i + 1 is achievable; the answer is the last index where it holds.

from typing import List


def hIndex(citations: List[int]) -> int:
    citations.sort(reverse=True)
    h = 0
    for i, c in enumerate(citations):
        if c >= i + 1:
            h = i + 1
        else:
            break
    return h

Walkthrough on Example 1, citations = [3,0,6,1,5]:

1. Sorted descending: [6, 5, 3, 1, 0].
2. i=0: 6 ≥ 1 → h = 1.
3. i=1: 5 ≥ 2 → h = 2.
4. i=2: 3 ≥ 3 → h = 3.
5. i=3: 1 ≥ 4 fails → stop. Answer 3.

Complexity: O(n log n) time for the sort, O(1) extra space (in-place sort; Timsort uses up to O(n) internally).

Approach 3 — Counting buckets (O(n))

The h-index can never exceed n, so a paper with 900 citations contributes no more than one with exactly n citations. Clamp every count to n. The values then lie in the range 0..n, small enough for counting sort: tally how many papers take each value instead of comparing papers. Bucket the papers, then sweep h from n downward keeping a running total of papers with ≥ h citations; the first h at which the total reaches h is the answer.

from typing import List


def hIndex(citations: List[int]) -> int:
    n = len(citations)
    buckets = [0] * (n + 1)
    for c in citations:
        buckets[min(c, n)] += 1

    papers_with_at_least_h = 0
    for h in range(n, -1, -1):
        papers_with_at_least_h += buckets[h]
        if papers_with_at_least_h >= h:
            return h
    return 0

Walkthrough on Example 1, citations = [3,0,6,1,5], n = 5:

1. Clamped values: 3, 0, 5 (from 6), 1, 5 → buckets = [1, 1, 0, 1, 0, 2].
2. h=5: total = 2; 2 < 5.
3. h=4: total = 2 + 0 = 2; 2 < 4.
4. h=3: total = 2 + 1 = 3; 3 ≥ 3 → return 3.

Complexity: O(n) time, O(n) space for the buckets.

Common pitfalls

• Forgetting to clamp counts at n in the bucket version — buckets[c] with c up to 1000 either overflows the array or wastes space and, worse, breaks the ”≥ n is as good as n” sweep.
• Off-by-one between 0-based index and paper count in the sorted scan: index i means i + 1 papers, so the test is citations[i] >= i + 1, not >= i.
• Returning n blindly when all papers are highly cited — the loop forms above handle it, but ad-hoc early exits often miss the all-large case ([100] → 1, not 100).
• Sorting ascending and mixing up the condition (citations[i] >= n - i is the ascending-order form — pick one orientation and stay consistent).

Pattern takeaway

When the answer is provably bounded by n (here h ≤ number of papers), values above n carry no extra information — clamp them and the domain shrinks enough for counting sort / bucket tallies to replace comparison sorting. “Bound the answer, then count into buckets indexed by the bound” converts many O(n log n) rank/threshold problems into O(n).