Problem 331938 · medium · Phase 03 Linear Management & Searching

H-Index of a Sorted Citation List

binary search · arrays

citations is sorted in non-decreasing order; citations[i] is how often paper i was cited. The h-index is the largest h such that at least h papers have at least h citations each. Return it.

Examples

Input:  citations = [0, 1, 3, 5, 6]
Output: 3
Explanation: three papers (3, 5, 6) have at least 3 citations; four papers do not have at least 4.

Input:  citations = [1, 2, 100]
Output: 2

Input:  citations = [0, 0]
Output: 0

Constraints

  • 0 <= len(citations) <= 10**6, 0 <= citations[i] <= 10**9
  • Required time: O(log n).

Goals

  • Express the h-index condition in terms of an index into the sorted list
  • Return the count derived from the boundary, not the boundary itself
Starting Python…