H-Index
Medium Counting sort
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
citations[i] is how many citations paper i has. The h-index is the largest h such that at least h papers have h or more citations each. Return it.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the biggest h where at least h papers have h or more citations.
Why this works: h can't exceed n, so bucket citations (capping at n) and walk from high to low, adding up papers.
Example: [3, 0, 6, 1, 5], n = 5
buckets: 0→1, 1→1, 3→1, 5→2 (6 capped to 5)h=5: 2 papers, h=4: 2, h=3: 3 ≥ 3 → answer 3
✦Hints open one at a time
↗Approach
Count papers per citation value (capped at n). Scan h from n down to 0 keeping a running total of papers with ≥ h citations; the first h where the total reaches h is the answer.
</>Solution (Java)
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int[] bucket = new int[n + 1];
for (int c : citations) bucket[Math.min(c, n)]++;
int papers = 0;
for (int h = n; h >= 0; h--) {
papers += bucket[h]; // papers with at least h citations
if (papers >= h) return h;
}
return 0;
}
}!Common mistake
Off-by-one when sorting: after sorting ascending, the check is citations[i] >= n - i, not > .
- Time: O(n).
- Space: O(n).
