H-Index
Medium · Arrays & Hashing · Explanation and code example
Citation Buckets
How it works
An h-index cannot exceed the number of papers. Bucket every citation count at its value capped to n. Scanning downward accumulates the number of papers with at least the current candidate h; the first candidate with at least h papers is the maximum valid answer.
Steps
- Count citations into n + 1 capped buckets.
- Scan candidate h values downward while accumulating papers.
- Return the first h whose accumulated count is at least h.
Complexity
- Time: O(n).
- Space: O(n).
Things to watch for
- Citations above n belong in the n bucket.
- The h-index counts papers, rather than total citations.
- All zero citations produce zero.
Python code example
from itertools import accumulate
class Solution:
def hIndex(self, citations: list[int]) -> int:
n = len(citations)
accumulate = 0
count = [0] * (n + 1)
for citation in citations:
count[min(citation, n)] += 1
# To find the maximum h-index, loop from the back to the front.
# i := the candidate's h-index
for i, c in reversed(list(enumerate(count))):
accumulate += c
if accumulate >= i:
return i
C++ code example
class Solution {
public:
int hIndex(vector<int>& citations) {
const int n = citations.size();
int accumulate = 0;
vector<int> count(n + 1);
for (const int citation : citations)
++count[min(citation, n)];
// To find the maximum h-index, loop from the back to the front.
// i := the candidate's h-index
for (int i = n; i >= 0; --i) {
accumulate += count[i];
if (accumulate >= i)
return i;
}
throw;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.