Why it works
- 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.
- 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.
- 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 ↗