H-Index

The key idea

Sort the citations in descending order. Walk the sorted list keeping a 1-based rank i+1. As long as the paper at rank i+1 has at least i+1 citations, you have that many papers with that many citations, so the h-index can grow to i+1. The first rank where the paper has fewer citations than its rank is where the h-index stops.

Problem

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i-th paper, return the researcher's h-index.

The h-index is defined as the maximum value h such that the given researcher has published at least h papers that have each been cited at least h times.

Constraints

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

Examples

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

Input: citations = [1,3,1] Output: 1

Complexity

Time: O(n log n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →