The problem
Given citation counts per paper, return the largest h such that at least h papers have ≥ h citations each.
Stuck? Reveal hints one at a time
How to approach it
- 1Build a count array of size n + 1; count[min(citations, n)]++ per paper.
- 2Scan h from n down to 0, keeping a running total of papers with ≥ h citations.
- 3The first h where the running total ≥ h is the answer.
Key insight
Clamping to n is what makes counting sort applicable — the answer space is [0, n] regardless of how large individual citation counts get.
The solution
Watch out for
- h = 0 always qualifies, so the loop always returns — the final return 0 is belt-and-braces.
- The sort-based version (sort desc, find last i with citations[i] > i) is O(n log n) and fine to mention first.