Compute a researcher's h-index from their papers' citation counts. Test your code, then compare with the explained solution. Free online practice.

H-Index – Solve Online

Reverse Integer

Compute a researcher's h-index from their papers' citation counts.

Given an array `citations` where `citations[i]` is the number of citations a researcher's `i`-th paper received, return the researcher's **h-index**.

The h-index is defined as the maximum value `h` such that the researcher has published **at least `h` papers that have each been cited at least `h` times**.

**Input / output**
- Input: `citations: int[]`
- Output: `int` — the h-index

## Examples
```
Input: {"citations":[3,0,6,1,5]}
Output: 3
```

```
Input: {"citations":[1,3,1]}
Output: 1
```

```
Input: {"citations":[6,5,3,1,0]}
Output: 3
```

Explanation for `[3,0,6,1,5]`: sorting gives `[6,5,3,1,0]`. Three papers have at least 3 citations each (6, 5, 3), and the remaining two have no more than 3, so the h-index is 3.

## Constraints
- `1 <= citations.length <= 5000`
- `0 <= citations[i] <= 1000`

## Follow-up
Can you compute the h-index in `O(n)` time without fully sorting, by bucketing every citation count above `n` into a single `n` bucket?

- The h-index is the largest `h` for which at least `h` papers each have `>= h` citations.
- Equivalently, if you sort citations in descending order, it is the largest `h` where the `h`-th most-cited paper (1-indexed) still has at least `h` citations.

Restate the definition

- Sort the citations in descending order.
- Walk the sorted list; while the paper at position `i` (0-indexed) has `>= i + 1` citations, the h-index is at least `i + 1`.
- The first position that fails this test ends the run, so the last satisfied `i + 1` is the answer.

Sort-and-scan approach

- Sorting dominates the cost: `O(n log n)` time, `O(1)` or `O(n)` extra space depending on the sort.

Sort-based solution

- Any citation count larger than `n` (the number of papers) can only ever contribute to an h-index of at most `n`, so clamp it into a single `n` bucket.
- Build `buckets[0..n]` counting how many papers have each (clamped) citation count.
- Sweep from the highest bucket down, accumulating how many papers have at least `i` citations; the first `i` where that running total reaches `i` is the h-index.

Bucket counts to drop the sort

- Counting sort over the clamped values gives linear time and `O(n)` space.

Optimal O(n) counting solution

- Comparing against `i` instead of `i + 1` when scanning a 0-indexed descending array.
- Forgetting to clamp citation counts above `n`, which breaks the bucket sizing.
- Returning after the first failure without having recorded the last valid `h` in the sort-based version.