Citation Impact Score

MediumSorting & Searching

Problem

A university rates researchers by an impact score: the largest number s such that the researcher has at least s papers with at least `s` citations each.

Given citations, where citations[i] is the citation count of paper i, return the impact score. Aim for linear time.

Example 1

Input:
citations = [4, 0, 6, 1, 5]
Output:
3

Three papers (4, 6, 5) have at least 3 citations; there are not four papers with at least 4.

Example 2

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

Example 3

Input:
citations = [0]
Output:
0

Constraints

  • 1 ≤ citations.length ≤ 10^5
  • 0 ≤ citations[i] ≤ 10^9

Hint

Show the first hint

After sorting descending, how could you read the score off the sorted list?

Walkthrough

How to approach it

01Clarify before coding

  • Can citation counts be huge? Yes, up to 10^9, so buckets must be capped.
  • Is a score of 0 possible? Yes, when no paper has any citation.
  • Is the input sorted? No.

02Brute force

Sort descending and find the last position i (1-based) where the i-th paper has at least i citations.

Cost: O(n log n) time: fine, but a counting approach gets O(n).

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.