H-Index
Medium · Arrays & Hashing · Array · Sorting · Counting Sort
Problem
A researcher has published n papers, and citations[i] is the number of times paper i has been cited.
The researcher's h-index is the largest number h such that at least h papers have at least h citations each. Return it.
The answer is always between 0 (no paper is cited) and n (every paper has at least n citations).
Examples
Input: citations = [3, 0, 6, 1, 5] Output: 3
Three papers (3, 6 and 5) have at least 3 citations; there are not four with at least 4.
Input: citations = [1, 3, 1] Output: 1
Every paper has at least 1 citation, but only one has 2 or more.
Input: citations = [0, 0] Output: 0
No paper is cited.
Constraints
- 1 <= n <= 5000
- 0 <= citations[i] <= 1000
Approaches
- Sort from most to least cited — time O(n log n), space O(n)
Follow-up
If papers arrive one at a time, can you report the h-index after each one without re-sorting? And how does the g-index, which lets the top papers share their citations, change the computation?
Related problems
Start free on Cariara · Coding problems · System design studio
