H-Index

Medium#274search the answer

You get the citation counts of a researcher's papers. Their h-index is the largest h such that h of the papers have at least h citations each. Find it. Our example: [6, 0, 3, 11, 1, 5] — the answer is 3: four papers have at least 3 citations, but only three have at least 4.

274 H-IndexWalkthrough · 1×

Example: Citations [6, 0, 3, 11, 1, 5], not sorted. The top row is the possible h, 0..6; below, the papers counted for h = mid.

possible h0123456locitations6031115count—
h still possiblemiddle, checked nowa paper with at least mid citationsruled outthe h-index

h = 0 always works: lo = 0

01/19
restart · back · play · step
Speed
1function hIndex(citations):
2 lo = 0
3 hi = len(citations) // h <= the number of papers
4 while lo < hi:
5 mid = ceil((lo + hi) / 2) // round up
6 count = papers with at least mid citations
7 if count >= mid:
8 lo = mid // h = mid works: keep it
9 else:
10 hi = mid - 1
11 return lo
state
lo
0
hi
–
mid
–
count
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. If h papers have at least h citations each, every smaller h works too. So over h = 0, 1, 2, … the checks go yes, …, yes, no, …, no, and the answer is the last yes.
  2. The search runs over the answer h, not over the array, so the citations need no sorting: each check just counts the papers with at least mid citations.
  3. lo = mid keeps an h that works, so mid is rounded up. Rounded down, with lo = 3 and hi = 4 it would be 3 again, and the range would never shrink.

Complexity

Time O(n log n): about log n values of h are tried, and each count walks over all n papers. Memory O(1). Counting the papers per citation number gives O(n), but this run shows the pattern.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.