DSA Factory
Free Mixed sets lessonsMixed sets · Stage 1 · Set 2 · Step 2

Enough papers cited enough times

Find the h-index of a sorted citation list by binary searching the position where the number of papers left meets the citations. About 12 minutes.

A condition that flips once

A researcher's papers are listed with their citations, sorted from fewest to most. The h-index is the largest h such that at least h papers have h or more citations. With a sorted list, look at position i: n minus i papers are at position i or later, and all of them have at least the citations at position i.

So if the citations at position i are at least n minus i, then n minus i papers qualify. This is false for early positions and true for later ones. It flips once, so you can search for the flip.

Condition: citations at i is at least papers from i on.
Flips once: false then true along the sorted list.
In code
n = len(cites)
at_mid = n - mid       # papers from mid on
ok = cites[mid] >= at_mid
Sorted citations 1, 2, 4, 4, 7, 9. Six papers.
1
0
2
1
4
2
4
3
7
4
9
5
leftright

The middle is position 2, with 4 citations. Four papers (positions 2 to 5) are at or after it. 4 is at least 4, so it works. Look earlier.

Move 1 of 3

The answer is what's left

The first position where the condition holds gives the biggest group, because earlier positions fail and a group starting later is smaller. The answer is the number of papers from that position to the end.

If the condition never holds, the search ends past the last position and the answer is 0 papers.

First position that works: gives the largest h.
Never works: the answer is 0.
Quick check

At position i, there are 4 papers from there on and the citation count is 6. Does the condition hold?

  1. AYes: 6 is at least 4
  2. BNo: 6 is more than 4
  3. CYou need the other papers
Show the answer

Yes: 6 is at least 4. Four papers each have at least 6 citations, so h could be 4.

Your problem

H-index of a sorted list

citations is a list of whole numbers sorted from smallest to largest, the number of times each of a researcher's papers has been cited. The h-index is the largest h such that at least h papers have h or more citations each. Return the h-index.

Example
citations = [0, 1, 3, 5, 6] → 3

0 ≤ papers ≤ 100,000 · 0 ≤ citations ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve