#274 H-Index

frequently reported atBloomberg Google Amazon Meta

the problem

In plain words

citations[i] is the citation count of paper i. Return the largest h such that the researcher has at least h papers with at least h citations each.

in citations = [3,0,6,1,5]

out 3

Papers with 3, 6, 5 citations: three papers with ≥ 3.

in citations = [1,3,1]

out 1

1 ≤ n ≤ 5000
0 ≤ citations[i] ≤ 1000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternCounting / bucket sort

h can never exceed n, so citation counts above n all behave the same — put them in one bucket and counting sort becomes O(n).

solutions

From brute force to optimal

For h = n down to 1, count papers with ≥ h citations.

For each h from n down, count c ≥ h.
Return the first h whose count ≥ h.

timeO(n²)

Up to n candidates × an O(n) count.

spaceO(1)

A counter.

javajava.util.*

1class Solution {2    public int hIndex(int[] citations) {3        int n = citations.length;4        for (int h = n; h > 0; h--) {           // try the biggest h first5            int atLeastH = 0;6            for (int c : citations) if (c >= h) atLeastH++;7            if (atLeastH >= h) return h;8        }9        return 0;10    }11}

In sorted order, papers i..n−1 all have ≥ c[i] citations; the first i with c[i] ≥ n − i gives h = n − i.

Sort.
For i from 0: if c[i] ≥ n − i, return n − i.
Return 0.

timeO(n log n)

Sorting dominates.

spaceO(n)

We sort a copy (O(log n) if sorting in place).

javajava.util.*

1class Solution {2    public int hIndex(int[] citations) {3        int[] c = citations.clone();4        Arrays.sort(c);                          // ascending5        int n = c.length;6        for (int i = 0; i < n; i++) {7            if (c[i] >= n - i) return n - i;     // papers i..n-1 (n-i of them) all have ≥ n-i citations8        }9        return 0;10    }11}

buckets[c] = papers with exactly c citations (c capped at n). Walk h from n down, accumulating.

buckets[min(c, n)]++.
papers = 0; for h = n..0: papers += buckets[h]; if papers ≥ h return h.

timeO(n)

Two linear passes over n + 1 buckets.

spaceO(n)

The bucket array.

javajava.util.*

1class Solution {2    public int hIndex(int[] citations) {3        int n = citations.length;4        int[] buckets = new int[n + 1];          // buckets[n] collects every paper with ≥ n citations5        for (int c : citations) buckets[Math.min(c, n)]++;6        int papers = 0;                          // papers with ≥ h citations7        for (int h = n; h >= 0; h--) {8            papers += buckets[h];9            if (papers >= h) return h;10        }11        return 0;12    }13}

in the room

How to say it in the interview

talk track

Explain the definition with a tiny example first — the definition is the hard part.
Then say: "h ≤ n, so I can cap counts at n and bucket them."

traps

Returning c[i] instead of n − i in the sorted scan.

what they ask next

Follow-ups

H-Index II (LC 275): citations already sorted?

Binary search for the first i with c[i] ≥ n − i — O(log n).

before you submit

Edge cases to test

Nobody cited anything ([0, 0, 0]) → 0.
One paper with 100 citations → 1: h can't exceed the number of papers.
Every paper cited more than n times → n.

practise next