Problem Description
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 of h such that the given researcher has published at least h papers that have each been cited at least h times.
Key Insights
- The h-index is determined by finding a number h such that there are at least h papers with at least h citations each.
- Sorting the array of citations allows for an easier count of how many papers meet the criteria for each potential h-index.
- An efficient approach is to sort the array and then iterate through it to find the maximum h-index.
Space and Time Complexity
Time Complexity: O(n log n) - The dominant factor is the sorting of the citations array.
Space Complexity: O(1) - We are using a constant amount of additional space.
Solution
To solve the problem, we will first sort the citations array in non-decreasing order. After sorting, we will iterate through the citations and for each index i, we will check if the number of papers (n-i) with at least citations[i] citations is greater than or equal to citations[i]. The maximum value of citations[i] that satisfies this condition will be our h-index.