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.

Put differently: find the biggest h for which the claim “h of my papers each got h or more citations” is true. h can never exceed the number of papers.

Examples

Example 1: citations = [3,0,6,1,5] → 3 Three papers (3, 6, 5 citations) each have ≥ 3 citations; four papers with ≥ 4 each doesn’t hold (only 6 and 5 qualify).

Example 2: citations = [1,3,1] → 1 Only one paper has ≥ 2 citations, so h = 2 fails; h = 1 holds (three papers have ≥ 1… one suffices).

Example 3: citations = [100] → 1 One paper, however famous, caps h at 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 naive intuition: h ranges over 0..n. For each candidate h, count how many papers have ≥ h citations and keep the largest h that works.

from typing import List


class Solution:
    def hIndex(self, 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’s 2.5·10^7 comparisons — it squeaks by here, but it does n passes where one suffices and collapses at the next order of magnitude.

Approach 2 — Sort descending, scan

The insight: 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


class Solution:
    def hIndex(self, 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 insight: the h-index can never exceed n, so a paper with 900 citations contributes exactly as much as one with n citations — clamp every count to n. Now the values live in the tiny range 0..n, which invites counting sort (tally how many items take each value instead of comparing items). Bucket the papers, then sweep h from n downward keeping a running total of papers with ≥ h citations; the first h the total reaches is the answer.

from typing import List


class Solution:
    def hIndex(self, 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).