Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, return the researcher's h-index.
According to the definition of h-index on Wikipedia: 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.
You must write an algorithm that runs in logarithmic time.
Example 1:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
Example 2:
Input: citations = [1,2,100] Output: 2
Constraints:
n == citations.length1 <= n <= 1050 <= citations[i] <= 1000citations is sorted in ascending order.Given the array is sorted, we can efficiently search for the h-index using binary search, aiming for logarithmic time complexity. The idea is to use the binary search to find the maximum h such that citations[h] ≥ h.
The C solution defines a function hIndex using binary search to find the h-index. It utilizes a loop to adjust left and right boundaries based on comparison, reducing the search space logarithmically.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n).
Space Complexity: O(1).
In this linear scan approach, we traverse the sorted citations list from beginning to end. The goal is to determine the maximum valid h-index by checking citations against their corresponding paper count.
This C implementation uses a simple loop to check each citation's sufficiency against its position in the list, returning the calculated h-index when the condition is satisfied.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(log n). |
| Linear Scan Approach | Time Complexity: O(n). |
H index | Leetcode #274 • Techdose • 53,608 views views
Watch 9 more video solutions →Practice H-Index II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor