{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

H-Index – Solution & Complexity

Interview solutions
/
H-Index

Solution Walkthrough

  1. Step 1: Restate the definition

    • The h-index is the largest h for which at least h papers each have >= h citations.
    • Equivalently, if you sort citations in descending order, it is the largest h where the h-th most-cited paper (1-indexed) still has at least h citations.

  2. Step 2: Sort-and-scan approach

    • Sort the citations in descending order.
    • Walk the sorted list; while the paper at position i (0-indexed) has >= i + 1 citations, the h-index is at least i + 1.
    • The first position that fails this test ends the run, so the last satisfied i + 1 is the answer.

  3. Step 3: Sort-based solution

    • Sorting dominates the cost: O(n log n) time, O(1) or O(n) extra space depending on the sort.
    def h_index(citations: list[int]) -> int:
    citations.sort(reverse=True)
    h = 0
    for i, c in enumerate(citations):
        if c >= i + 1:
            h = i + 1
        else:
            break
    return h

  4. Step 4: Bucket counts to drop the sort

    • Any citation count larger than n (the number of papers) can only ever contribute to an h-index of at most n, so clamp it into a single n bucket.
    • Build buckets[0..n] counting how many papers have each (clamped) citation count.
    • Sweep from the highest bucket down, accumulating how many papers have at least i citations; the first i where that running total reaches i is the h-index.

  5. Step 5: Optimal O(n) counting solution

    • Counting sort over the clamped values gives linear time and O(n) space.
    def h_index(citations: list[int]) -> int:
    n = len(citations)
    buckets = [0] * (n + 1)
    for c in citations:
        buckets[min(c, n)] += 1
    count = 0
    for i in range(n, -1, -1):
        count += buckets[i]
        if count >= i:
            return i
    return 0

  6. Step 6: Common mistakes

    • Comparing against i instead of i + 1 when scanning a 0-indexed descending array.
    • Forgetting to clamp citation counts above n, which breaks the bucket sizing.
    • Returning after the first failure without having recorded the last valid h in the sort-based version.

FAQ

See also

Practice H-Index online (run code in the browser)3Sum solution (medium)3Sum Closest solution (medium)Combination Sum II solution (medium)Merge Intervals solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?