Problem 372484 · medium · Phase 03 Linear Management & Searching

Citation Impact Score

sorting · sort-then-scan · counting

A researcher's impact score is the largest integer h such that at least h of their papers have at least h citations each.

Given the list citations (one entry per paper), return the impact score.

Examples

Input:  citations = [3, 0, 6, 1, 5]
Output: 3
Explanation: Three papers (3, 6, 5) have at least 3 citations, but only two have at least 4.
Input:  citations = [1, 3, 1]
Output: 1

Constraints

  • 0 <= len(citations) <= 10**5
  • 0 <= citations[i] <= 10**6
  • Target complexity: O(n log n).

Goals

  • Translate a threshold definition into a scan over a sorted list
  • Relate a value to its position in descending order
  • Return the largest threshold that still holds
Starting Python…