H Index From Citations
Problem
A researcher's h-index is the largest number h such that at least h of their papers have h or more citations each. Given the citation count of every paper, return the h-index.
Examples
Input: citations = [3, 0, 6, 1, 5]
Output: 3
Why: three papers have at least 3 citations; four papers with 4 or more do not existInput: citations = [1, 1]
Output: 1
Why: one paper has at least 1 citation, but two papers with 2 or more do notInput: citations = [0]
Output: 0
Why: edge case, an uncited paper gives an h-index of zeroHints
0 / 3
Trying every candidate h from 0 upwards works, but each try re-counts the same papers. Consider what order would let one pass answer all the candidates.
If the papers are lined up from most cited to least, the position of a paper already tells you how many papers are at least as good as it.
Sort descending and walk the list. At position i, exactly i+1 papers have that many citations or more, so the condition is simply whether the paper at i has at least i+1 citations. The last position that holds is the answer.
Solution
Sorting descending turns the definition into a single comparison per paper: at zero-based position i there are i + 1 papers with at least this citation count, so the h-index is the last position where the count still reaches i + 1. Because the sorted counts only fall while the required bar only rises, the test fails once and never recovers — so the scan can stop at the first failure. Time is O(n log n) for the sort, space O(1) beyond it.
def h_index(citations):
citations.sort(reverse=True) # most cited first
h = 0
for i, c in enumerate(citations):
if c >= i + 1: # i+1 papers have at least c citations
h = i + 1
else:
break # counts fall, the bar rises: no recovery
return h
print(h_index([3, 0, 6, 1, 5])) # -> 3
print(h_index([1, 1])) # -> 1
print(h_index([0])) # -> 0Stuck on the idea rather than the code? Sorting Basics covers it.