medium

H-Index

Compute a researcher's h-index from a list of citation counts.

1. Define the problem

H-Index

You are given an array of integers citations where citationsi is the number of citations a researcher received for their ith paper. Return the researcher's h-index . Rather than sorting the citations, tally every value into a count array sized n + 1 — clamping any citation at or above n into the last bucket — then scan the buckets from the top down , accumulating a running total of papers seen so far until that total first meets or exceeds the bucket index.

Constraints

  • n == citations.length
  • 1 ≤ n ≤ 5000
  • 0 ≤ citationsi ≤ 1000

Example

Inputcitations = [3, 0, 6, 1, 5]
Output3

Explanation The researcher has 3 papers with at least 3 citations each ([3, 6, 5]), and the remaining papers have no more than 3 citations, so the h-index is 3.

2. Know the words first

In plain terms

H-index
The largest number h such that the researcher has at least h papers that have each been cited at least h times.
3. Visualize the solution

Bucket every citation count, then scan buckets from the top down

Bucket every citation count, then scan buckets from the top down
Statusbucket 3

citations=[3, 0, 6, 1, 5], n=5. citations[0]=3 → bucket 3.

What happens in this step

citations[0] = 3, n = 5. Since 3 < n, buckets[3]++.

buckets = [0, 0, 0, 1, 0, 0]

3 is below n, so it gets its own bucket rather than being clamped.
Step 1 of 6

Steps to visualize

  1. Size a bucket array to n + 1, one bucket per possible h-index value from 0 to n.
  2. Tally each citation into its bucket, clamping any value at or above n into the last bucket.
  3. Walk the buckets from n down to 0, adding each bucket to a running total.
  4. The first index where the running total meets or exceeds that index is the h-index.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Bucket every citation count, then scan buckets from the top down
Statusbucket 3

citations=[3, 0, 6, 1, 5], n=5. citations[0]=3 → bucket 3.

What happens in this step

citations[0] = 3, n = 5. Since 3 < n, buckets[3]++.

buckets = [0, 0, 0, 1, 0, 0]

3 is below n, so it gets its own bucket rather than being clamped.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function hIndex(citations) {
  const n = citations.length;
  const buckets = new Array(n + 1).fill(0);

  for (const c of citations) {
    if (c >= n) buckets[n]++;
    else buckets[c]++;
  }

  let total = 0;

  for (let i = n; i >= 0; i--) {
    total += buckets[i];
    if (total >= i) {
      return i;
    }
  }

  return 0;
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
citations = [3, 0, 6, 1, 5]3example from the docstring
citations = [1, 3, 1]1small citation counts capping the h-index at 1
citations = [0, 0, 0]0no citations at all
citations = [100]1a single highly-cited paper caps the h-index at n
citations = [5, 5, 5, 5]4every paper has at least n citations, so h-index equals n
citations = [10, 8, 5, 4, 3]4citation values spanning a wide range clamp correctly
citations = [0, 1, 3, 5, 6]3mixed low and high citation counts

Keep reading