Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The h-index is the largest h such that at least h papers each have ≥ h citations. Sort the citations ascending: the answer is the largest n−i for which citations[i] ≥ n−i (because positions i..n−1 are the n−i papers with the most citations). That's O(n log n). A counting-bucket pass that caps each citation at n hits O(n) time and O(n) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can translate a self-referential definition into a precise condition (citations[i] ≥ n−i), and whether you know counting buckets give O(n) when values are bounded by n.
Where candidates slip
Misreading the definition (using > instead of ≥, or 'exactly h' instead of 'at least h'), or returning i instead of the count n−i after sorting.
How to stand out
Give the sort solution with a crisp justification of the n−i condition, then offer the O(n) counting-bucket because h can never exceed n — capping at n is the key insight.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCompute h-indexInput already sorted?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Sort + Threshold Scan
1Hint 1Explore hintHide hint
If you sort the citations, the papers with the most citations cluster together. How many papers have at least as many citations as the one at sorted position i?
2Hint 2Explore hintHide hint
Sort ascending. At position i, the papers i, i+1, …, n−1 are the n−i most-cited papers, all with ≥ citations[i] citations.
3Hint 3Explore hintHide hint
So if citations[i] ≥ n−i, then those n−i papers each clear the bar of n−i → h = n−i. Scan left to right and return the first such n−i.
A · Core idea
Sorting turns the self-referential definition into a clean geometric crossover. After an ascending sort, the array reads from least-cited to most-cited, so any suffix i..n−1 is precisely 'the n−i most-cited papers'.
The condition, derived. Fix a sorted position i. The papers at indices i, i+1, …, n−1 number exactly n−i, and because the array is ascending, every one of them has at least citations[i] citations. So if citations[i] ≥ n−i, we have found n−i papers each with ≥ n−i citations — that's a valid h = n−i. The definition asks for the maximum such h.
Why the first hit scanning left-to-right is the maximum. As i increases, the candidate h = n−i decreases (n−0, n−1, n−2, …). So the very first i (smallest i) at which citations[i] ≥ n−i holds yields the largest h. We return immediately; no need to keep scanning. If we never find one, every paper falls short and the answer is 0.
Why ascending and `n−i`, not descending and `i+1`. Both work — they're mirror images. Descending sort lets you return i+1 at the first citations[i] < i+1 break, while ascending lets you return n−i at the first citations[i] ≥ n−i. I use ascending because int[] sorts ascending natively in Java (no boxing to reverse it), keeping the code clean in both languages. The reasoning is identical; pick whichever you can explain without fumbling.
Why this is correct but not optimal. Sorting is O(n log n), and that's perfectly acceptable for n ≤ 5000. But the citation values are bounded, and h can never exceed n — that ceiling is the door to a linear-time counting solution, which is the upgrade an interviewer will nudge you toward.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
citations = [3,0,6,1,5]Array state
i=0
h=5, 0 ≥ 5? no
3C · Code with teaching comments
Reference implementation previewpublic int hIndex(int[] citations) { Arrays.sort(citations); int n = citations.length; for (int i = 0; i < n; i++) { int h = n - i;Explore the full codeHide the full code
D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Sort, then read each suffix as 'the k most-cited papers'. The h-index is the largest k where the k-th-from-top paper still has ≥ k citations — a value-meets-rank crossover that the first qualifying position reveals.
ComplexityO(n log n) time, O(1) space — Sorting dominates at O(n log n). The single scan is O(n) and uses no extra space beyond the in-place sort → O(1) auxiliary space.
E · Edge cases and pitfalls6citations = [100] — Sorted [100], i=0 h=1, 100 ≥ 1 → return 1 (one paper, can't exceed n=1).Explore edge casesHide edge cases
Edge cases handled
citations = [100]Sorted [100], i=0 h=1, 100 ≥ 1 → return 1 (one paper, can't exceed n=1).citations = [0]i=0 h=1, 0 ≥ 1? no → return 0.citations = [1,1]Sorted [1,1], i=0 h=2 1≥2 no; i=1 h=1 1≥1 yes → 1.
Pitfalls
- Returning i instead of n−i — confuses position with paper count.
- Using > instead of ≥ — the definition is 'at least h citations'.
- Sorting descending in Java with Arrays.sort on int[] — it only sorts ascending; you'd need Integer[] boxing.
Approach 2 of 2 · Optimal
Counting Buckets (Optimal O(n))
1Hint 1Explore hintHide hint
The h-index can never exceed the number of papers n. What if you grouped papers by citation count, lumping everything ≥ n into one bucket?
2Hint 2Explore hintHide hint
Make buckets[0..n] where buckets[j] = number of papers with exactly j citations, but put any citation > n into buckets[n].
3Hint 3Explore hintHide hint
Sweep from j = n down to 0, accumulating how many papers have ≥ j citations. The first j where that running total ≥ j is the h-index.
A · Core idea
Sorting is overkill because the answer lives in a tiny range [0, n]. That ceiling lets us replace comparison sorting with counting.
Why capping at n is sound. A paper with 1000 citations and a paper with exactly n citations are interchangeable for the h-index: both can only ever help reach an h of at most n (you can't have more than n qualifying papers). So we collapse every citation count ≥ n into a single bucket index n. This keeps the bucket array size at n+1 regardless of how large individual citation values get — turning the bounded-answer observation into bounded memory.
The high-to-low sweep computes a suffix count. After bucketing, buckets[j] is 'papers with citation count exactly j' (with j = n meaning 'n or more'). Walking j from n down to 0 and accumulating total += buckets[j] makes total equal 'number of papers with at least j citations'. That running total is exactly the left side of the h-index test: we want the largest j such that at least `j` papers have at least `j` citations, i.e. total ≥ j.
Why the first j (largest) that satisfies total ≥ j is the answer. Because we sweep j downward from n, the first time total ≥ j holds is for the largest qualifying j. The total only grows as j decreases (we keep adding buckets), and the bar j only shrinks, so once the condition becomes true it gives the maximal h. Return it immediately.
Why this is strictly better asymptotically. Two linear passes, no log factor. For huge inputs with bounded values this is the textbook win, and it's a clean demonstration that you can exploit value bounds — the same trick behind counting sort and bucket-based selection.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
citations = [3,0,6,1,5]Interactive diagram
Choosing an h-index method
j=5Sort if values are unbounded; bucket-count when values are bounded by n; binary search if already sorted.
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
When the answer is bounded by n, count instead of sort. Capping citations at n keeps the bucket array small; a high-to-low sweep converts buckets into a suffix count, and the first j with (papers ≥ j) ≥ j is the h-index.
ComplexityO(n) time, O(n) space — Filling buckets is one O(n) pass; the high-to-low sweep is O(n). Total O(n) time, with an O(n)-sized bucket array → O(n) space.
E · Edge cases and pitfalls6citations = [0,0,0] — All in bucket 0. j sweeps 3,2,1: total stays 0; j=0: total += 3, 3 ≥ 0 → return 0.Explore edge casesHide edge cases
Edge cases handled
citations = [0,0,0]All in bucket 0. j sweeps 3,2,1: total stays 0; j=0: total += 3, 3 ≥ 0 → return 0.citations = [4,4,4,4]All capped to bucket 4 (n=4). j=4: total=4, 4 ≥ 4 → return 4.citations = [1000]n=1, capped to bucket 1. j=1: total=1, 1 ≥ 1 → return 1.
Pitfalls
- Forgetting to cap with min(c, n) — array index out of bounds for large citations.
- Sweeping low→high — you'd find the smallest j, not the largest.
- Using > instead of >= in the total check — off-by-one on exact-fit cases like [4,4,4,4].
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int hIndex(int[] citations) { int n = citations.length; int[] buckets = new int[n + 1]; for (int c : citations) { buckets[Math.min(c, n)]++;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Using strict > instead of >=
The definition is 'at least h citations'. With >, a paper cited exactly h times is wrongly excluded, undercounting h (e.g. [3,3,3] should give 3, not 2).
Explore the code comparisonHide the code comparison
Using strict > instead of >=
The definition is 'at least h citations'. With >, a paper cited exactly h times is wrongly excluded, undercounting h (e.g. [3,3,3] should give 3, not 2).
Don't write this
if citations[i] > n - i:
return n - iWrite this instead
if citations[i] >= n - i:
return n - i2Returning the index instead of the count
After sorting, position i is not the answer; the number of qualifying papers is n−i. Returning i gives a meaningless value.
Explore the code comparisonHide the code comparison
Returning the index instead of the count
After sorting, position i is not the answer; the number of qualifying papers is n−i. Returning i gives a meaningless value.
Don't write this
for (int i = 0; i < n; i++) {
if (citations[i] >= n - i) return i;
}Write this instead
for (int i = 0; i < n; i++) {
if (citations[i] >= n - i) return n - i;
}3Not capping citations in the bucket method
A citation of 1000 with n = 5 would index buckets[1000] and crash. Cap at n because h can never exceed n.
Explore the code comparisonHide the code comparison
Not capping citations in the bucket method
A citation of 1000 with n = 5 would index buckets[1000] and crash. Cap at n because h can never exceed n.
Don't write this
buckets[c]++;Write this instead
buckets[Math.min(c, n)]++;Revise
Carry the pattern into the interview
Pattern to remember
Sort + threshold scan (or counting buckets for O(n))
Code pattern to memorize
sort ascending; n = len(citations)
for i in 0..n-1:
h = n - i # papers from i to end
if citations[i] >= h: return h
return 0Rules to remember
- 1h-index = max h with at least h papers each having ≥ h citations — read this definition twice.
- 2After ascending sort, the suffix
i..n−1holds exactlyn−ipapers; ifcitations[i] ≥ n−i, thenh = n−iworks. - 3Return the first such h while scanning ascending — it's the largest because
n−ishrinks asigrows. - 4h is capped at n (you can't have more qualifying papers than papers), which is what makes counting buckets O(n).
- 5Counting variant: bucket
min(c, n), then sweep high→low accumulating count untiltotal ≥ i.
Use this pattern when
- Find a threshold value defined self-referentially (h papers with ≥ h something)
- Rank-versus-value crossover problems on a multiset
- When values are bounded so counting/bucketing beats sorting
- Any 'largest k such that k items clear a bar of k'
Choose another pattern when
- Citations already sorted → binary search the crossover in O(log n) (that's H-Index II / LC 275)
- You need the actual papers, not just the count → track indices, not a tally
- Values are huge/unbounded → bucketing wastes memory; sort instead
- Definition is a simple max/min, not the self-referential h → no crossover needed
Interview takeaway
The h-index is a rank-meets-value crossover: sort and find where citations[i] catches up to the count of papers from i onward. Once you see it as 'where does value cross the remaining-count line', the sort solution and the O(n) bucket both fall out naturally.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternRank-versus-value crossover solved by sorting, with a counting-bucket upgrade when the answer is bounded by n. Recognise it whenever a quantity is defined self-referentially ('k items each clearing a bar of k') — sort to find the crossover, or count when values are bounded.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- H-Index IIComing soonInput is already sorted — binary search the crossover in O(log n).
- Sort Integers by The Number of 1 BitsComing soonCounting/bucketing by a bounded key, the same lens as bucketing citations.
- First Missing PositiveComing soonAnother bounded-answer trick: the result lies in [1, n+1], enabling O(n) via in-place bucketing.
- Sort an ArrayComing soonCounting sort applies when values are bounded — the engine behind the O(n) h-index.