Hi👋SpeedAlgo • Deliberate Practice & Cognitive Ergonomics for Software Engineers

An interactive algorithm mastery and technical interview preparation platform published by Hi👋WebEnterprise. Built for senior and staff software engineers preparing for rigorous coding screens at top tech companies (FAANG/MAMAA).

13 Core Algorithmic Patterns & 225 Practice Problems

  • 1. Two Pointers (16 Paradigms, 43 Problems): Opposite ends, sorted pair sums, palindrome verification, trapping rain water, 3Sum, container with most water — includes the Sliding Window and Fast & Slow Pointers paradigms (contiguous subarray invariants, longest substrings, Floyd's cycle detection, linked list middle).
  • 2. Binary Search (9 Paradigms, 14 Problems): Monotonic predicate partitioning (feasible(x)), boundary search, rotated sorted arrays, square roots, minimum ship capacity, median of two sorted arrays, matrix median on value range.
  • 3. Bit Manipulation (5 Paradigms, 11 Problems): Counting set bits, XOR cancellation, bit reversal, bitmask pairing, maximum XOR with a bitwise trie.
  • 4. Math & Geometry (8 Paradigms, 14 Problems): Sieve of Eratosthenes, integer/roman conversions, modular arithmetic, geometric simulation.
  • 5. Tree/Graph Depth-First Search (15 Paradigms, 24 Problems): Path sums, lowest common ancestor, tree diameter, validating BSTs, tree DP (House Robber III, Binary Tree Cameras).
  • 6. Tree/Graph Breadth-First Search (5 Paradigms, 12 Problems): Level-order traversals, shortest path in unweighted graphs, zig-zag traversals, rotting oranges, word ladders.
  • 7. Graphs (12 Paradigms, 22 Problems): Topological sort, cycle detection, Dijkstra's algorithm, bipartite graph validation, network delay.
  • 8. Backtracking (6 Paradigms, 14 Problems): Subsets, permutations, combinations, constraint satisfaction, pruning, N-Queens, Sudoku solver.
  • 9. Dynamic Programming (13 Paradigms, 28 Problems): Memoization vs tabulation, 0/1 knapsack, unbounded knapsack, coin change, edit distance, longest common subsequence.
  • 10. Heap / Priority Queue (9 Paradigms, 11 Problems): Running medians, top-k elements, interval scheduling, IPO, k-way merges.
  • 11. Advanced Data Structures (7 Paradigms, 17 Problems): Trie (prefix tree), Union-Find (Disjoint Set Union), LRU Cache, LFU Cache, range-sum queries with updates.
  • 12. Stack (5 Paradigms, 9 Problems): Next greater element, largest rectangle in histogram, remove k digits, decode string, min stack.
  • 13. Intervals & Greedy (2 Paradigms, 6 Problems): Merge intervals, interval scheduling, meeting rooms by sweep line, jump game.

4-Stage Deliberate Practice Framework

  1. Stage 1 (Compare & Learn): Read the pattern's mental model, loop invariant and Big-O proof, compare the pattern's template with the problem's solution side by side, and use the step-by-step debugger. The solution can also be shown in C#, Java, TypeScript, C++, Go or Rust for almost every problem.
  2. Stage 2 (Active Recall): Rebuild the solution from memory in a code editor, with an invariant checklist and optional progressive hints, and check it against a judged test suite.
  3. Stage 3 (AI Interview Coach, coming soon): A mock-interview stage still in development; for now, students go straight from Stage 2 to Stage 4.
  4. Stage 4 (Solve on Your Own): Solve a new problem on your own against a 15-minute timer; your code is graded against a test suite. Python and TypeScript run in your browser and C# runs on our server (design problems grade in Python and TypeScript).

Equipped with a spaced-repetition review hub on a fixed 7-step schedule (1 day up to 90 days), a two-pane Studio workspace, and study notes.

Pricing, Access & Commercial Terms

  • Core Curriculum: 100% Free. No credit card required.
  • Coins: New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins.
  • AI Coach: Each AI coach question costs 1-5 coins, priced by the server according to its size.
  • BYOK (Bring Your Own Key): AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK).
  • Extras: Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1).
  • Payments & Refunds: Nothing on the site is sold for money: coins can only be earned, never bought. There are no subscriptions or charges, so there is nothing to refund.
  • Platform Operator: Hi👋WebEnterprise. Support & policies at hispeedalgo.com.
Skip to main content
Hi👋SpeedAlgo

Invariant-First Algorithmic Mastery

Arena
238Items
Theory Context•Two Pointers & Sliding Window

Builds on Bucket Sort, which you haven’t finished yet.

P2MediumBuilt on Bucket Sort~3 min speedrun

Counting Sort (H-Index, Maximum Ice Cream Bars)

Built on
Bucket SortThe values are small whole numbers, so each value gets its own slot instead of a range of values.
The problem

H-Index (LC 274)(opens leetcode.com)

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.

Example 1
Input:citations = [3,0,6,1,5]
Output:3
Five papers. Three of them (with 6, 5 and 3 citations) have at least 3 each, so h = 3 works. h = 4 would need four papers with 4 or more citations, and only two (6 and 5) have that.
3001621354>= 3>= 3>= 3

Counting Sort

Spot it when: The values are whole numbers in a small range that you know in advance. Examples: prices up to 105, heights up to 100, or a count that can never be more than n. You need the values in sorted order, or the smallest, the largest or the k-th of them. A comparison sort takes O(n log n) time, and you want less.
Not this one if…
  • The values spread over a huge range, up to 109 in Maximum Gap (LC 164). A list with one slot per value would be too large to build. Each bucket must cover a range of values instead. See Bucket Sort
  • The question is only "have I seen this value?" or "how many of each value?", with no order, as in Contains Duplicate (LC 217). The values reach 109. A hash map keyed by value holds only the values that occur. See Hash Map
  • The citations arrive already sorted, and the answer must take O(log n) time, as in H-Index II (LC 275). Reading every paper to count it would already be too slow. See Lower Bound
Counting Sort
Python
1def h_index(citations: list[int]) -> int:
2 """H-Index: Counting Sort with every count of n or more kept in slot n.
3 Time: O(N) | Space: O(N)
4 """
5 n = len(citations)
6 # count[c]: papers with exactly c citations, for c from 0 to n; count[n] also catches every
7 # paper with n or more citations, since the h-index can never exceed n.
8 count = [0] * (n + 1)
9 
10 # 1. Drop Each Paper Into Its Citation Slot, Capped At n:
11 # No two papers are compared; capping at n keeps a paper with huge citations inside the list
12 # and treats it the same as a paper with exactly n citations, which is all h-index can need.
13 for c in citations:
14 count[min(c, n)] += 1
15 
16 # 2. Walk h Down From n Until Enough Papers Qualify:
17 # papers always holds the number of papers with at least h citations; each step down adds
18 # the papers with exactly the new h, so the first h with papers >= h is the largest h that
19 # works.
20 h = n
21 papers = count[n]
22 while papers < h:
23 h -= 1
24 papers += count[h]
25 
26 return h
Invariant: After the counting loop, count[v] is the number of papers with exactly v citations. The last slot, count[n], holds the papers with n or more citations. During the walk, papers is the number of papers with at least h citations.

Counting Sort sorts without comparing two values. It works when every value is a whole number in a small range that you know in advance. Make one slot for each possible value. For each value v, add 1 to its slot with count[v] += 1. Then read the slots from the smallest value to the largest. This visits the values in sorted order. In H-Index (LC 274), the loop reads the slots from the top, h = n, down to 0. Each time h goes down by 1, papers adds count[h]. So papers is always the number of papers with at least h citations. The first h where papers >= h is the largest h that works, and that is the answer. This is correct because a slot's position is its value. The slots are already in order, so no comparison is needed. The trap is the size of the list. A paper can have up to 1000 citations, but n can be 1. Then count[c] += 1 writes past the end of a list with n + 1 slots. The h-index can never be larger than n. So a paper with more than n citations counts the same way as a paper with exactly n. Write count[min(c, n)] += 1. The list then needs only n + 1 slots, whatever the citations are.

See it run

Counting Sort, step by step

c - · h - · papers -

c 3 · h - · papers -

c 0 · h - · papers -

c 6 · h - · papers -

c 1 · h - · papers -

c 5 · h - · papers -

c - · h 5 · papers 2

c - · h 4 · papers 2

c - · h 3 · papers 3

c - · h 3 · papers 3 · answer 3

The top row is count, one slot for each number of citations from 0 to n. The bottom row is papers, the number of papers with at least h citations, filled in as the walk goes down.

  • put the slot that receives one paper
  • cap slot n, which also holds a paper with more than n citations
  • h the slot read by the walk, while papers < h
  • stop the slot where papers >= h, which gives the answer

Start: n = 5, so count has 6 slots, numbered 0 to 5. Every slot is 0.

c = 3, so count[3] becomes 1. No paper is compared with another paper.

c = 0, so count[0] becomes 1. No paper is compared with another paper.

Trap: c = 6 is more than n = 5, and count has no slot 6. count[min(6, 5)] is count[5], and it becomes 1.

c = 1, so count[1] becomes 1. No paper is compared with another paper.

c = 5, so count[5] becomes 2. No paper is compared with another paper.

h = 5 and papers = count[5] = 2. papers < h, so the walk goes on.

h = 4, so papers = papers + count[4] = 2. papers < h, so the walk goes on.

h = 3, so papers = papers + count[3] = 3. papers >= h, so the walk stops.

Done: 3 papers have at least 3 citations, so the h-index is 3.

count
00
10
20
30
40
50
papers
1 / 10
Gotchas1 of 3

Gotcha 1 of 3

  1. 1
    The trap

    Gotcha 1: Indexing count[c] without the cap at n

    Mistake
    count[c] += 1
    Fix
    count[min(c, n)] += 1

    What happens: count has only n + 1 slots, numbered 0 to n. A paper can have more citations than n. Then count[c] is past the end of the list, and Python raises an IndexError. The h-index can never be larger than n, so slot n can hold every paper with n or more citations.

    Example: citations = [100]
    Mistake: raises IndexErrorFix: returns 1
  2. 2

    Gotcha 2: Stopping only when papers == h

    Mistake
    while papers != h:
    Fix
    while papers < h:

    What happens: papers can jump past h in one step. Then papers is never equal to h, and the loop keeps lowering h below 0. Python reads count[-1], count[-2] and so on from the end of the list. The index finally goes out of range, and Python raises an IndexError.

    Example: citations = [1, 1, 1]
    Mistake: raises IndexErrorFix: returns 1
  3. 3

    Gotcha 3: Adding count[h] before lowering h

    Mistake
    papers += count[h]
h -= 1
    Fix
    h -= 1
papers += count[h]

    What happens: At the start, papers already holds count[n]. Adding before lowering adds count[n] a second time. Every later total is too large, so the loop can stop at an h that is too large.

    Example: citations = [3, 0, 6, 1, 5]
    Mistake: returns 4Fix: returns 3

Deep Dive

What this card adds: one slot for each exact value

Bucket Sort gives each bucket a range of values. Counting Sort is the case where the values are small whole numbers, so a bucket never needs a range. Slot v counts the values that are exactly v.

The procedure has two loops. The first loop does count[v] += 1 for every value. The second loop reads the slots from the smallest value to the largest, or the reverse. The position of a slot is its value, so the slots are already in order and no comparison is needed.

The size of the list is the range of the values plus one. This is why the card needs a small, known range. A range up to 105 is fine. A range up to 109, as in Maximum Gap (LC 164), is too large, and Bucket Sort is the right tool there.

H-Index, traced on five papers

Take citations = [3, 0, 6, 1, 5]. Here n = 5, so count has 6 slots, numbered 0 to 5.

The first loop adds the papers. The paper with 3 citations goes to count[3]. The paper with 0 goes to count[0]. The paper with 6 is marked as the trap on the board. Slot 6 does not exist, so min(6, 5) puts the paper in count[5]. The paper with 1 goes to count[1]. The paper with 5 also goes to count[5], which is now 2.

The walk starts with h = 5 and papers = count[5] = 2. Since 2 < 5, the loop lowers h to 4 and adds count[4] = 0, so papers stays 2. Then h = 3 and papers = 2 + count[3] = 3.

Now papers >= h, because 3 >= 3, so the walk stops. The h-index is 3: three papers have at least 3 citations. The LeetCode example [3, 0, 6, 1, 5] has the answer 3.

Why the cap and the stop test are correct

The h-index can never be larger than n, because it needs h papers and there are only n. So a paper with more than n citations counts the same as a paper with exactly n. The cap count[min(c, n)] += 1 keeps the list at n + 1 slots. Without the cap, citations = [100] raises an IndexError.

While the walk goes down, papers is the number of papers with at least h citations. Each step down to h adds the papers with exactly h citations. Going down makes h smaller and papers larger, so the first h with papers >= h is the largest h that works.

Use while papers < h, not papers != h. For citations = [1, 1, 1], papers goes from 0 to 3 at h = 1, so it is never equal to h. With !=, h keeps falling below 0 and the code raises an IndexError. The correct code stops at h = 1.

The order inside the loop matters too. Lower h first, then add count[h]. If the code adds first, it counts count[n] twice, and [3, 0, 6, 1, 5] returns 4 instead of 3.

Cost, and a second use

The first loop reads n values and the walk visits at most n + 1 slots. The time is O(n) and the space is O(n). A comparison sort costs O(n log n). In general, with m slots, the time is O(n + m) and the space is O(m).

Maximum Ice Cream Bars (LC 1833) uses the same procedure. The costs are at most 105. Count the bars by cost, then walk the prices from 1 upward. At each price, buy min(count[price], coins // price) bars and subtract their cost from coins. Stop when a price cannot be bought in full. For costs = [1, 3, 2, 4, 1] and coins = 7, the answer is 4, and this matches a sort-first version on 20000 random inputs.

60-Second Pitch

"The h-index is at most n, and sorting would cost O(n log n). So I use one slot for each citation count from 0 to n. A paper with more than n citations goes in slot n, because it counts the same as a paper with exactly n. Then I walk h down from n and keep papers, the number of papers with at least h citations. I stop at the first h where papers >= h, and that is the largest h that works. The time is O(n) and the space is O(n). If the values were spread up to 109, I would use ranges instead of exact slots, which is Bucket Sort."

Common Questions

How is Counting Sort different from Bucket Sort?

Bucket Sort gives each bucket a range of values and needs extra work inside a bucket. Counting Sort gives each exact value its own slot, so a slot holds only a count and nothing needs to be compared. It needs a small range of values.

Why is the list size n + 1 and not the largest citation count?

The h-index cannot be larger than n. A paper with more than n citations counts the same as one with exactly n, so slot n holds all of them. The list needs only n + 1 slots, even when a paper has 1000 citations.

Why does the walk go down from n and not up from 0?

Going down, papers only grows and h only shrinks. So the first h with papers >= h is the largest one that works, and the walk can stop there. Going up, the test would need the count of papers at or above h, which is a suffix sum that the walk does not have yet.

How does H-Index II (LC 275) change the answer?

The citations are already sorted and the answer must take O(log n) time. Counting reads every paper, which is O(n), so it is too slow. Use binary search on the sorted list.

When is a hash map better than a count list?

When the values reach 109 but few of them occur, as in Contains Duplicate (LC 217). A list with one slot for each possible value would be too large. A hash map holds only the values that occur, but it gives no order.

SWE Reasoning

Spot it

  • Every value is a whole number in a small range that is known before the data is read: prices up to 105, heights up to 100, or a count that can never be more than n.
  • The question needs the values in order, or the k-th, smallest or largest of them, as in H-Index (LC 274) and Maximum Ice Cream Bars (LC 1833).
  • A comparison sort works but costs O(n log n), and the limit asks for less.

The invariant, step by step

  1. count has n + 1 slots, all 0.
  2. For each paper with c citations, count[min(c, n)] += 1. After the loop, count[v] is the number of papers with exactly v citations, and count[n] holds the papers with n or more.
  3. The walk starts at h = n with papers = count[n].
  4. While papers < h, lower h by 1 and add count[h] to papers.
  5. At every moment, papers is the number of papers with at least h citations. The first h with papers >= h is the answer.

Traps

  • No cap at n. count[c] += 1 with c = 100 and n = 1 raises an IndexError.
  • The test papers != h. papers can jump past h, and h then keeps falling below 0.
  • Adding count[h] before lowering h. This counts count[n] twice, and [3, 0, 6, 1, 5] returns 4 instead of 3.

Practice

Canonical LeetCode:H-Index (LC 274)Maximum Ice Cream Bars (LC 1833)Height Checker (LC 1051)Relative Sort Array (LC 1122)Minimum Number of Moves to Seat Everyone (LC 2037)Minimum Increment to Make Array Unique (LC 945)
Theory Context•Two Pointers & Sliding Window

Builds on Bucket Sort, which you haven’t finished yet.

P2MediumBuilt on Bucket Sort~3 min speedrun

Counting Sort (H-Index, Maximum Ice Cream Bars)

Built on
Bucket SortThe values are small whole numbers, so each value gets its own slot instead of a range of values.
The problem

H-Index (LC 274)(opens leetcode.com)

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.

Example 1
Input:citations = [3,0,6,1,5]
Output:3
Five papers. Three of them (with 6, 5 and 3 citations) have at least 3 each, so h = 3 works. h = 4 would need four papers with 4 or more citations, and only two (6 and 5) have that.
3001621354>= 3>= 3>= 3

Counting Sort

Spot it when: The values are whole numbers in a small range that you know in advance. Examples: prices up to 105, heights up to 100, or a count that can never be more than n. You need the values in sorted order, or the smallest, the largest or the k-th of them. A comparison sort takes O(n log n) time, and you want less.
Not this one if…
  • The values spread over a huge range, up to 109 in Maximum Gap (LC 164). A list with one slot per value would be too large to build. Each bucket must cover a range of values instead. See Bucket Sort
  • The question is only "have I seen this value?" or "how many of each value?", with no order, as in Contains Duplicate (LC 217). The values reach 109. A hash map keyed by value holds only the values that occur. See Hash Map
  • The citations arrive already sorted, and the answer must take O(log n) time, as in H-Index II (LC 275). Reading every paper to count it would already be too slow. See Lower Bound
Counting Sort
Python
1def h_index(citations: list[int]) -> int:
2 """H-Index: Counting Sort with every count of n or more kept in slot n.
3 Time: O(N) | Space: O(N)
4 """
5 n = len(citations)
6 # count[c]: papers with exactly c citations, for c from 0 to n; count[n] also catches every
7 # paper with n or more citations, since the h-index can never exceed n.
8 count = [0] * (n + 1)
9 
10 # 1. Drop Each Paper Into Its Citation Slot, Capped At n:
11 # No two papers are compared; capping at n keeps a paper with huge citations inside the list
12 # and treats it the same as a paper with exactly n citations, which is all h-index can need.
13 for c in citations:
14 count[min(c, n)] += 1
15 
16 # 2. Walk h Down From n Until Enough Papers Qualify:
17 # papers always holds the number of papers with at least h citations; each step down adds
18 # the papers with exactly the new h, so the first h with papers >= h is the largest h that
19 # works.
20 h = n
21 papers = count[n]
22 while papers < h:
23 h -= 1
24 papers += count[h]
25 
26 return h
Invariant: After the counting loop, count[v] is the number of papers with exactly v citations. The last slot, count[n], holds the papers with n or more citations. During the walk, papers is the number of papers with at least h citations.

Counting Sort sorts without comparing two values. It works when every value is a whole number in a small range that you know in advance. Make one slot for each possible value. For each value v, add 1 to its slot with count[v] += 1. Then read the slots from the smallest value to the largest. This visits the values in sorted order. In H-Index (LC 274), the loop reads the slots from the top, h = n, down to 0. Each time h goes down by 1, papers adds count[h]. So papers is always the number of papers with at least h citations. The first h where papers >= h is the largest h that works, and that is the answer. This is correct because a slot's position is its value. The slots are already in order, so no comparison is needed. The trap is the size of the list. A paper can have up to 1000 citations, but n can be 1. Then count[c] += 1 writes past the end of a list with n + 1 slots. The h-index can never be larger than n. So a paper with more than n citations counts the same way as a paper with exactly n. Write count[min(c, n)] += 1. The list then needs only n + 1 slots, whatever the citations are.

See it run

Counting Sort, step by step

c - · h - · papers -

c 3 · h - · papers -

c 0 · h - · papers -

c 6 · h - · papers -

c 1 · h - · papers -

c 5 · h - · papers -

c - · h 5 · papers 2

c - · h 4 · papers 2

c - · h 3 · papers 3

c - · h 3 · papers 3 · answer 3

The top row is count, one slot for each number of citations from 0 to n. The bottom row is papers, the number of papers with at least h citations, filled in as the walk goes down.

  • put the slot that receives one paper
  • cap slot n, which also holds a paper with more than n citations
  • h the slot read by the walk, while papers < h
  • stop the slot where papers >= h, which gives the answer

Start: n = 5, so count has 6 slots, numbered 0 to 5. Every slot is 0.

c = 3, so count[3] becomes 1. No paper is compared with another paper.

c = 0, so count[0] becomes 1. No paper is compared with another paper.

Trap: c = 6 is more than n = 5, and count has no slot 6. count[min(6, 5)] is count[5], and it becomes 1.

c = 1, so count[1] becomes 1. No paper is compared with another paper.

c = 5, so count[5] becomes 2. No paper is compared with another paper.

h = 5 and papers = count[5] = 2. papers < h, so the walk goes on.

h = 4, so papers = papers + count[4] = 2. papers < h, so the walk goes on.

h = 3, so papers = papers + count[3] = 3. papers >= h, so the walk stops.

Done: 3 papers have at least 3 citations, so the h-index is 3.

count
00
10
20
30
40
50
papers
1 / 10
Gotchas1 of 3

Gotcha 1 of 3

  1. 1
    The trap

    Gotcha 1: Indexing count[c] without the cap at n

    Mistake
    count[c] += 1
    Fix
    count[min(c, n)] += 1

    What happens: count has only n + 1 slots, numbered 0 to n. A paper can have more citations than n. Then count[c] is past the end of the list, and Python raises an IndexError. The h-index can never be larger than n, so slot n can hold every paper with n or more citations.

    Example: citations = [100]
    Mistake: raises IndexErrorFix: returns 1
  2. 2

    Gotcha 2: Stopping only when papers == h

    Mistake
    while papers != h:
    Fix
    while papers < h:

    What happens: papers can jump past h in one step. Then papers is never equal to h, and the loop keeps lowering h below 0. Python reads count[-1], count[-2] and so on from the end of the list. The index finally goes out of range, and Python raises an IndexError.

    Example: citations = [1, 1, 1]
    Mistake: raises IndexErrorFix: returns 1
  3. 3

    Gotcha 3: Adding count[h] before lowering h

    Mistake
    papers += count[h]
h -= 1
    Fix
    h -= 1
papers += count[h]

    What happens: At the start, papers already holds count[n]. Adding before lowering adds count[n] a second time. Every later total is too large, so the loop can stop at an h that is too large.

    Example: citations = [3, 0, 6, 1, 5]
    Mistake: returns 4Fix: returns 3

Deep Dive

What this card adds: one slot for each exact value

Bucket Sort gives each bucket a range of values. Counting Sort is the case where the values are small whole numbers, so a bucket never needs a range. Slot v counts the values that are exactly v.

The procedure has two loops. The first loop does count[v] += 1 for every value. The second loop reads the slots from the smallest value to the largest, or the reverse. The position of a slot is its value, so the slots are already in order and no comparison is needed.

The size of the list is the range of the values plus one. This is why the card needs a small, known range. A range up to 105 is fine. A range up to 109, as in Maximum Gap (LC 164), is too large, and Bucket Sort is the right tool there.

H-Index, traced on five papers

Take citations = [3, 0, 6, 1, 5]. Here n = 5, so count has 6 slots, numbered 0 to 5.

The first loop adds the papers. The paper with 3 citations goes to count[3]. The paper with 0 goes to count[0]. The paper with 6 is marked as the trap on the board. Slot 6 does not exist, so min(6, 5) puts the paper in count[5]. The paper with 1 goes to count[1]. The paper with 5 also goes to count[5], which is now 2.

The walk starts with h = 5 and papers = count[5] = 2. Since 2 < 5, the loop lowers h to 4 and adds count[4] = 0, so papers stays 2. Then h = 3 and papers = 2 + count[3] = 3.

Now papers >= h, because 3 >= 3, so the walk stops. The h-index is 3: three papers have at least 3 citations. The LeetCode example [3, 0, 6, 1, 5] has the answer 3.

Why the cap and the stop test are correct

The h-index can never be larger than n, because it needs h papers and there are only n. So a paper with more than n citations counts the same as a paper with exactly n. The cap count[min(c, n)] += 1 keeps the list at n + 1 slots. Without the cap, citations = [100] raises an IndexError.

While the walk goes down, papers is the number of papers with at least h citations. Each step down to h adds the papers with exactly h citations. Going down makes h smaller and papers larger, so the first h with papers >= h is the largest h that works.

Use while papers < h, not papers != h. For citations = [1, 1, 1], papers goes from 0 to 3 at h = 1, so it is never equal to h. With !=, h keeps falling below 0 and the code raises an IndexError. The correct code stops at h = 1.

The order inside the loop matters too. Lower h first, then add count[h]. If the code adds first, it counts count[n] twice, and [3, 0, 6, 1, 5] returns 4 instead of 3.

Cost, and a second use

The first loop reads n values and the walk visits at most n + 1 slots. The time is O(n) and the space is O(n). A comparison sort costs O(n log n). In general, with m slots, the time is O(n + m) and the space is O(m).

Maximum Ice Cream Bars (LC 1833) uses the same procedure. The costs are at most 105. Count the bars by cost, then walk the prices from 1 upward. At each price, buy min(count[price], coins // price) bars and subtract their cost from coins. Stop when a price cannot be bought in full. For costs = [1, 3, 2, 4, 1] and coins = 7, the answer is 4, and this matches a sort-first version on 20000 random inputs.

60-Second Pitch

"The h-index is at most n, and sorting would cost O(n log n). So I use one slot for each citation count from 0 to n. A paper with more than n citations goes in slot n, because it counts the same as a paper with exactly n. Then I walk h down from n and keep papers, the number of papers with at least h citations. I stop at the first h where papers >= h, and that is the largest h that works. The time is O(n) and the space is O(n). If the values were spread up to 109, I would use ranges instead of exact slots, which is Bucket Sort."

Common Questions

How is Counting Sort different from Bucket Sort?

Bucket Sort gives each bucket a range of values and needs extra work inside a bucket. Counting Sort gives each exact value its own slot, so a slot holds only a count and nothing needs to be compared. It needs a small range of values.

Why is the list size n + 1 and not the largest citation count?

The h-index cannot be larger than n. A paper with more than n citations counts the same as one with exactly n, so slot n holds all of them. The list needs only n + 1 slots, even when a paper has 1000 citations.

Why does the walk go down from n and not up from 0?

Going down, papers only grows and h only shrinks. So the first h with papers >= h is the largest one that works, and the walk can stop there. Going up, the test would need the count of papers at or above h, which is a suffix sum that the walk does not have yet.

How does H-Index II (LC 275) change the answer?

The citations are already sorted and the answer must take O(log n) time. Counting reads every paper, which is O(n), so it is too slow. Use binary search on the sorted list.

When is a hash map better than a count list?

When the values reach 109 but few of them occur, as in Contains Duplicate (LC 217). A list with one slot for each possible value would be too large. A hash map holds only the values that occur, but it gives no order.

SWE Reasoning

Spot it

  • Every value is a whole number in a small range that is known before the data is read: prices up to 105, heights up to 100, or a count that can never be more than n.
  • The question needs the values in order, or the k-th, smallest or largest of them, as in H-Index (LC 274) and Maximum Ice Cream Bars (LC 1833).
  • A comparison sort works but costs O(n log n), and the limit asks for less.

The invariant, step by step

  1. count has n + 1 slots, all 0.
  2. For each paper with c citations, count[min(c, n)] += 1. After the loop, count[v] is the number of papers with exactly v citations, and count[n] holds the papers with n or more.
  3. The walk starts at h = n with papers = count[n].
  4. While papers < h, lower h by 1 and add count[h] to papers.
  5. At every moment, papers is the number of papers with at least h citations. The first h with papers >= h is the answer.

Traps

  • No cap at n. count[c] += 1 with c = 100 and n = 1 raises an IndexError.
  • The test papers != h. papers can jump past h, and h then keeps falling below 0.
  • Adding count[h] before lowering h. This counts count[n] twice, and [3, 0, 6, 1, 5] returns 4 instead of 3.

Practice

Canonical LeetCode:H-Index (LC 274)Maximum Ice Cream Bars (LC 1833)Height Checker (LC 1051)Relative Sort Array (LC 1122)Minimum Number of Moves to Seat Everyone (LC 2037)Minimum Increment to Make Array Unique (LC 945)
© 2026 Hi👋WebEnterprise. All rights reserved.
Sitemap•llms.txt•