H-Index (LeetCode 274)
A researcher has published n papers, and citations[i] is the number of times paper i has been cited. Their h-index is the largest number h for which at least h of the papers each have h or more citations.
Return the researcher's h-index.
Worked Examples
citations = [3,0,6,1,5]3citations = [1,3,1]1⚖️Formal Constraints & Bounds
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
Core Insight
The h-index can never be larger than n, the number of papers. So a paper with more than n citations counts the same as a paper with n. The code uses n + 1 slots and fills them in one loop, with no comparisons. It then walks from h = n down and adds up the slots. At each h, the running total is the number of papers with at least h citations.
Real-World Scenario & Production Applications
Some questions ask for a threshold that depends on a count. One example is an author's h-index in a citation database. Another is the largest k such that k servers each have k or more free slots. Counting the items per value, up to the number of items, answers each question in two passes. No sort is needed.
Step-by-Step Execution Trace Table
The debugger's first preset is Example 1, citations = [3,0,6,1,5]. Here n = 5, so count has slots 0 to 5. The counting loop puts 3, 0, 1 and 5 into the slots with the same numbers. It puts 6 into slot min(6, 5) = 5. After the loop, count = [1, 1, 0, 1, 0, 2]. The walk then goes as follows:
h | count[h] added | papers | papers < h? |
|---|---|---|---|
| 5 | count[5] = 2 (the start) | 2 | 2 < 5 is true, so lower h |
| 4 | count[4] = 0 | 2 | 2 < 4 is true, so lower h |
| 3 | count[3] = 1 | 3 | 3 < 3 is false, so return 3 |
| 1 | Don't sort. The h-index is at most `n`, so only the citation values from 0 to `n` matter. Give each value its own slot and count the papers in each slot. Put every count of `n` or more into slot `n`. |
| 2 | While `h` goes down from `n`, keep `papers` equal to the number of papers with at least `h` citations. The first `h` with `papers >= h` is the answer. |
| 3 | The shape of the code: make a list of `n + 1` zeros. In one `for` loop, add 1 to each paper's slot. Then set `h = n` and `papers = count[n]`. In a `while papers < h` loop, lower `h` by 1 and add `count[h]`. Return `h`. |
| 4 | The trap is the slot index. Write `count[min(c, n)] += 1`, so every paper with `n` or more citations goes into slot `n`. On `[100]`, `n = 1` and the list has 2 slots. Without `min`, `count[100] += 1` raises an IndexError. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting solves this problem. Sort the citations from most cited to least cited. The h-index is then the last position h whose paper still has h or more citations. A comparison sort takes O(N log N) time. But the values here are whole numbers. Also, only the values from 0 to n matter, because the h-index can never be larger than the number of papers. Counting Sort uses these two facts. Make one slot for each value: count = [0] * (n + 1). Add each paper to the slot of its citation count with count[min(c, n)] += 1. No two papers are compared. The slots are already in order of value. So walk them from h = n down to 0 and add them up. At each h, the total is the number of papers with at least h citations.
🗂️ The Analogy: Exam Papers in Mark Trays
A teacher has 30 exam papers with marks from 0 to 100. The teacher wants them in order of mark. The teacher does not compare papers two at a time. Instead, the teacher sets out one tray for each mark and puts each paper into the tray for its mark. Then the teacher picks up the trays from 100 down to 0, and the papers come out in order. For the h-index, the trays only go up to n. A paper with more citations than there are papers goes into the top tray. Any count of n or more tells us the same thing about h.
🔑 Why It Works
After the counting loop, count[v] is the number of papers with exactly v citations, for every v below n. count[n] is the number of papers with n or more citations. During the walk, papers adds count[h] each time h goes down by 1. So papers is always the number of papers with at least h citations. As h goes down, papers can only go up. So the first h with papers >= h is the largest h that works. The loop always ends. At h = 0, the test papers >= 0 is always true.
Indexing
count[c]without the cap atnStopping only when
papers == hAdding
count[h]before loweringh
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for "the largest h such that at least h papers have h or more citations". Every citation is between 0 and 1000, and there are at most 5000 papers. The answer comes from the papers in sorted order, and the values are small whole numbers. Small whole-number values in a known range are the signal for Counting Sort. Here the range can be cut to 0 to n, because the answer can never be larger than the number of papers.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
While h goes down from n, papers is the number of papers with at least h citations. It starts as papers = count[n]. After each h -= 1, the code runs papers += count[h]. Stop at the first h with papers >= h. That h is the largest one that works.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Write
count[min(c, n)] += 1, so every paper withnor more citations goes into slotn. On[100],n = 1and the list has 2 slots. Withoutmin,count[100] += 1raises an IndexError.Keep the condition
while papers < h. Do not testpapers == h. On[1,1,1],papersjumps from 0 to 3 whenhreaches 1, so an==test never stops at the answer.Lower
hfirst, then addcount[h]. If you add first, the loop addscount[n]twice. Then[3,0,6,1,5]returns 4 instead of 3.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Counting Sort. The h-index can never be larger than the number of papers, n. So only citation values from 0 to n matter, and a count above n works exactly like n. I make n plus 1 slots. I add each paper to the slot of its citation count, capped at n. No two papers are ever compared. Then I walk h down from n. I keep a running total of the papers with at least h citations. Each time I lower h, I add the papers with exactly h citations. The first h where the total reaches h is the largest h that works. At h equal to 0 the test always passes, so the loop ends. The trap is the cap. Citations go up to 1000 while n can be 1, so without the cap the index goes past the end of the list. The time is
O(n)and the space isO(n).
Complexity & Mathematical Proof
O(N)
Look at the code. count = [0] * (n + 1) writes n + 1 zeros, which is O(N). The for c in citations loop does one min and one addition per paper, which is O(N). The while papers < h loop lowers h by 1 each time. It stops at h = 0 at the latest, because papers is never negative. So it runs at most n times, with O(1) work each time, which is O(N). The total is O(N). The size of the citation values does not change the cost. Because of the cap, the list has n + 1 slots whether a paper has 5 citations or 1000.
O(N)
count holds n + 1 integers, which is O(N). h and papers are two numbers, and the answer is one integer.
T(N) = O(N + 1) + N · O(1) + at most N · O(1) = O(N)
Derivation Progression
O(N + 1)
count = [0] * (n + 1) writes one zero per possible answer.
N · O(1)
The for c in citations loop does one min(c, n) and one += 1 for each paper.
at most N · O(1)
Each step of while papers < h does h -= 1 and one addition. h never goes below 0.
O(N)
One pass over the papers and at most one pass over the slots.
Variable Definitions
Number of papers, len(citations) (called n in the code)
The candidate h-index, walking down from n
Number of papers with at least h citations
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N): count, n + 1 integers
O(1): one integer
Boundary Best / Worst Cases
. The counting loop reads every paper, even when the walk stops at once, as in [5,5,5,5,5]
. Every paper is counted, and h walks from n down to 0, as in [0,0,0]
Senior SWE Deconstruction & Hardware Caveats
Triggers: "at least h papers", "h or more citations", "0 <= citations[i] <= 1000". The answer comes from the values in sorted order, and the values are small whole numbers. This points to Counting Sort. The range can be cut to 0 to n, because the h-index can never be larger than n.
At these limits, a sort would also be fast. The cap matters when the values grow. A citation database can hold papers with hundreds of thousands of citations. The slot list still has only n + 1 entries, one for each possible answer.
The papers may be spread over several shards (servers that each hold part of the data). Each shard can build its own count over the same slots. To merge, add the counts slot by slot, then walk the merged list once. Every shard must cap at the total number of papers n, not at its own number of papers. Otherwise a paper with more citations than its shard has papers goes into the wrong slot.
Core Algorithmic State Invariants
- Capping Loses Nothing
[3,0,6,1,5] and [3,0,1000,1,5] build the same list, count = [1, 1, 0, 1, 0, 2]. So both answers are 3. A paper with 6 citations and a paper with 1000 are both counted in every papers total from h = 5 down. The walk cannot tell them apart.
- When Every Paper Has 0 Citations
On [0,0,0], count = [3, 0, 0, 0]. papers stays 0 while h goes 3, 2, 1. Only at h = 0 does papers become 3. The test 3 >= 0 ends the loop, so the answer 0 needs no special case.
H-Index (LeetCode 274)
A researcher has published n papers, and citations[i] is the number of times paper i has been cited. Their h-index is the largest number h for which at least h of the papers each have h or more citations.
Return the researcher's h-index.
Worked Examples
citations = [3,0,6,1,5]3citations = [1,3,1]1⚖️Formal Constraints & Bounds
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
Core Insight
The h-index can never be larger than n, the number of papers. So a paper with more than n citations counts the same as a paper with n. The code uses n + 1 slots and fills them in one loop, with no comparisons. It then walks from h = n down and adds up the slots. At each h, the running total is the number of papers with at least h citations.
Real-World Scenario & Production Applications
Some questions ask for a threshold that depends on a count. One example is an author's h-index in a citation database. Another is the largest k such that k servers each have k or more free slots. Counting the items per value, up to the number of items, answers each question in two passes. No sort is needed.
Step-by-Step Execution Trace Table
The debugger's first preset is Example 1, citations = [3,0,6,1,5]. Here n = 5, so count has slots 0 to 5. The counting loop puts 3, 0, 1 and 5 into the slots with the same numbers. It puts 6 into slot min(6, 5) = 5. After the loop, count = [1, 1, 0, 1, 0, 2]. The walk then goes as follows:
h | count[h] added | papers | papers < h? |
|---|---|---|---|
| 5 | count[5] = 2 (the start) | 2 | 2 < 5 is true, so lower h |
| 4 | count[4] = 0 | 2 | 2 < 4 is true, so lower h |
| 3 | count[3] = 1 | 3 | 3 < 3 is false, so return 3 |
| 1 | Don't sort. The h-index is at most `n`, so only the citation values from 0 to `n` matter. Give each value its own slot and count the papers in each slot. Put every count of `n` or more into slot `n`. |
| 2 | While `h` goes down from `n`, keep `papers` equal to the number of papers with at least `h` citations. The first `h` with `papers >= h` is the answer. |
| 3 | The shape of the code: make a list of `n + 1` zeros. In one `for` loop, add 1 to each paper's slot. Then set `h = n` and `papers = count[n]`. In a `while papers < h` loop, lower `h` by 1 and add `count[h]`. Return `h`. |
| 4 | The trap is the slot index. Write `count[min(c, n)] += 1`, so every paper with `n` or more citations goes into slot `n`. On `[100]`, `n = 1` and the list has 2 slots. Without `min`, `count[100] += 1` raises an IndexError. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting solves this problem. Sort the citations from most cited to least cited. The h-index is then the last position h whose paper still has h or more citations. A comparison sort takes O(N log N) time. But the values here are whole numbers. Also, only the values from 0 to n matter, because the h-index can never be larger than the number of papers. Counting Sort uses these two facts. Make one slot for each value: count = [0] * (n + 1). Add each paper to the slot of its citation count with count[min(c, n)] += 1. No two papers are compared. The slots are already in order of value. So walk them from h = n down to 0 and add them up. At each h, the total is the number of papers with at least h citations.
🗂️ The Analogy: Exam Papers in Mark Trays
A teacher has 30 exam papers with marks from 0 to 100. The teacher wants them in order of mark. The teacher does not compare papers two at a time. Instead, the teacher sets out one tray for each mark and puts each paper into the tray for its mark. Then the teacher picks up the trays from 100 down to 0, and the papers come out in order. For the h-index, the trays only go up to n. A paper with more citations than there are papers goes into the top tray. Any count of n or more tells us the same thing about h.
🔑 Why It Works
After the counting loop, count[v] is the number of papers with exactly v citations, for every v below n. count[n] is the number of papers with n or more citations. During the walk, papers adds count[h] each time h goes down by 1. So papers is always the number of papers with at least h citations. As h goes down, papers can only go up. So the first h with papers >= h is the largest h that works. The loop always ends. At h = 0, the test papers >= 0 is always true.
Indexing
count[c]without the cap atnStopping only when
papers == hAdding
count[h]before loweringh
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for "the largest h such that at least h papers have h or more citations". Every citation is between 0 and 1000, and there are at most 5000 papers. The answer comes from the papers in sorted order, and the values are small whole numbers. Small whole-number values in a known range are the signal for Counting Sort. Here the range can be cut to 0 to n, because the answer can never be larger than the number of papers.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
While h goes down from n, papers is the number of papers with at least h citations. It starts as papers = count[n]. After each h -= 1, the code runs papers += count[h]. Stop at the first h with papers >= h. That h is the largest one that works.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Write
count[min(c, n)] += 1, so every paper withnor more citations goes into slotn. On[100],n = 1and the list has 2 slots. Withoutmin,count[100] += 1raises an IndexError.Keep the condition
while papers < h. Do not testpapers == h. On[1,1,1],papersjumps from 0 to 3 whenhreaches 1, so an==test never stops at the answer.Lower
hfirst, then addcount[h]. If you add first, the loop addscount[n]twice. Then[3,0,6,1,5]returns 4 instead of 3.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Counting Sort. The h-index can never be larger than the number of papers, n. So only citation values from 0 to n matter, and a count above n works exactly like n. I make n plus 1 slots. I add each paper to the slot of its citation count, capped at n. No two papers are ever compared. Then I walk h down from n. I keep a running total of the papers with at least h citations. Each time I lower h, I add the papers with exactly h citations. The first h where the total reaches h is the largest h that works. At h equal to 0 the test always passes, so the loop ends. The trap is the cap. Citations go up to 1000 while n can be 1, so without the cap the index goes past the end of the list. The time is
O(n)and the space isO(n).
Complexity & Mathematical Proof
O(N)
Look at the code. count = [0] * (n + 1) writes n + 1 zeros, which is O(N). The for c in citations loop does one min and one addition per paper, which is O(N). The while papers < h loop lowers h by 1 each time. It stops at h = 0 at the latest, because papers is never negative. So it runs at most n times, with O(1) work each time, which is O(N). The total is O(N). The size of the citation values does not change the cost. Because of the cap, the list has n + 1 slots whether a paper has 5 citations or 1000.
O(N)
count holds n + 1 integers, which is O(N). h and papers are two numbers, and the answer is one integer.
T(N) = O(N + 1) + N · O(1) + at most N · O(1) = O(N)
Derivation Progression
O(N + 1)
count = [0] * (n + 1) writes one zero per possible answer.
N · O(1)
The for c in citations loop does one min(c, n) and one += 1 for each paper.
at most N · O(1)
Each step of while papers < h does h -= 1 and one addition. h never goes below 0.
O(N)
One pass over the papers and at most one pass over the slots.
Variable Definitions
Number of papers, len(citations) (called n in the code)
The candidate h-index, walking down from n
Number of papers with at least h citations
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N): count, n + 1 integers
O(1): one integer
Boundary Best / Worst Cases
. The counting loop reads every paper, even when the walk stops at once, as in [5,5,5,5,5]
. Every paper is counted, and h walks from n down to 0, as in [0,0,0]
Senior SWE Deconstruction & Hardware Caveats
Triggers: "at least h papers", "h or more citations", "0 <= citations[i] <= 1000". The answer comes from the values in sorted order, and the values are small whole numbers. This points to Counting Sort. The range can be cut to 0 to n, because the h-index can never be larger than n.
At these limits, a sort would also be fast. The cap matters when the values grow. A citation database can hold papers with hundreds of thousands of citations. The slot list still has only n + 1 entries, one for each possible answer.
The papers may be spread over several shards (servers that each hold part of the data). Each shard can build its own count over the same slots. To merge, add the counts slot by slot, then walk the merged list once. Every shard must cap at the total number of papers n, not at its own number of papers. Otherwise a paper with more citations than its shard has papers goes into the wrong slot.
Core Algorithmic State Invariants
- Capping Loses Nothing
[3,0,6,1,5] and [3,0,1000,1,5] build the same list, count = [1, 1, 0, 1, 0, 2]. So both answers are 3. A paper with 6 citations and a paper with 1000 are both counted in every papers total from h = 5 down. The walk cannot tell them apart.
- When Every Paper Has 0 Citations
On [0,0,0], count = [3, 0, 0, 0]. papers stays 0 while h goes 3, 2, 1. Only at h = 0 does papers become 3. The test 3 >= 0 ends the loop, so the answer 0 needs no special case.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| One slot per possible answer | count = [0] * (n + 1) | `h` is a whole number from 0 to `n`. So slots 0 to `n` cover every possible answer. |
| Count each value in its own slot, capped at n (the trap) | for c in citations:
count[min(c, n)] += 1 | No two values are compared. A count above `n` works like `n`, because `h` can never be larger than the number of papers. The cap also keeps the index inside the list. |
| Start at the largest possible answer | h = n
papers = count[n] | `papers` holds the number of papers with at least `h` citations. At `h = n`, that is only the top slot. |
| Walk the slots down in order of value | while papers < h:
h -= 1
papers += count[h] | When `h` goes down by 1, the papers with exactly the new `h` citations are added. So `papers` stays the number of papers with at least `h` citations. |
| Answer | return h | The first `h` from the top with `papers >= h` is the largest `h` that works. |