244. H-Index II
You are given an integer array citations sorted in non-decreasing order, where citations[i] is the citation count of a researcher's i-th paper.
The researcher's h-index is the largest integer h such that at least h papers have h or more citations each. Return the h-index.
The sorted order is the whole point of this variant: aim for a solution that runs in O(log n) time.
Example 1:
Input: citations = [0, 1, 3, 5, 6]
Output: 3
Explanation: The three papers with 3, 5, and 6 citations each have at least 3, and no four papers reach 4, so h = 3.
Example 2:
Input: citations = [1, 2, 100]
Output: 2
Explanation: Two papers (2 and 100 citations) have at least 2 each; getting h = 3 would need all three papers at 3+, but the first has only 1.
Constraints:
- 1 ≤ citations.length ≤ 10⁵
- 0 ≤ citations[i] ≤ 1000
- citations is sorted in non-decreasing order.
Hints:
In sorted order, the suffix starting at index i contains exactly n - i papers, and every one of them has at least citations[i] citations. So index i certifies h = n - i whenever citations[i] >= n - i.
That predicate is monotone across the array: false for a prefix, then true for the rest. Binary search for the first index where it turns true and answer n minus that index (0 if it never does).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: citations = [0, 1, 3, 5, 6]
Expected output: 3