H-Index II
MedPrompt
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 non-descending 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] <= 1000citationsis sorted in ascending order.
Approaches
2 approaches with complexity analysis and trade-offs.
Iterate through the array and for each index check if it satisfies the h-index condition.
Algorithm
- Get the length of the array n
- Iterate through the array from index 0 to n-1
- For each index i:
- Calculate h = n - i (remaining papers)
- If citations[i] >= h, return h
- If no h-index found, return 0
Walkthrough
This approach involves iterating through the array from left to right. For each position i, we check if citations[i] is greater than or equal to the number of papers remaining (n-i). The first position where this condition is true gives us our h-index.
class Solution { public int hIndex(int[] citations) { int n = citations.length; for (int i = 0; i < n; i++) { int h = n - i; if (citations[i] >= h) { return h; } } return 0; }}The idea is that at each index i, we have n-i papers remaining (including the current one). If the current citation count is greater than or equal to the remaining papers, we've found our h-index.
Complexity
Time
O(n) where n is the length of the array
Space
O(1) constant space
Trade-offs
Pros
Simple to understand and implement
Works well for small arrays
No extra space required
Cons
Does not utilize the sorted nature of the array
Not optimal for large arrays
Does not meet the requirement of logarithmic time complexity
Use binary search to find the h-index by exploiting the sorted nature of the array.
Algorithm
- Initialize left = 0 and right = n-1
- While left <= right:
- Calculate mid = left + (right - left) / 2
- Calculate potential h-index h = n - mid
- If citations[mid] == h, return h
- If citations[mid] < h, search right half (left = mid + 1)
- If citations[mid] > h, search left half (right = mid - 1)
- Return n - left
Walkthrough
Since the array is sorted in ascending order, we can use binary search to find the h-index. The key insight is that for any index i, if citations[i] >= n-i, then n-i is a potential h-index. We want to find the largest such value.
class Solution { public int hIndex(int[] citations) { int n = citations.length; int left = 0; int right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; int h = n - mid; if (citations[mid] == h) { return h; } else if (citations[mid] < h) { left = mid + 1; } else { right = mid - 1; } } return n - left; }}The binary search maintains a window where the h-index could be. At each step:
- Calculate the middle point
- Compare citations[mid] with n-mid (potential h-index)
- If citations[mid] is too small, search right half
- If citations[mid] is too large, search left half
Complexity
Time
O(log n) where n is the length of the array
Space
O(1) constant space
Trade-offs
Pros
Meets the logarithmic time requirement
Efficiently utilizes the sorted nature of the array
Works well for large arrays
Cons
Slightly more complex to implement than linear search
Binary search implementation needs to be careful to handle edge cases
Solutions
Solution
class Solution {public int hIndex(int[] citations) { int n = citations.length; int left = 0, right = n; while (left < right) { int mid = (left + right + 1) >> 1; if (citations[n - mid] >= mid) { left = mid; } else { right = mid - 1; } } return left; }}public class Solution { public int HIndex(int[] citations) { int n = citations.Length; int left = 0, right = n; while (left < right) { int mid = (left + right + 1) >> 1; if (citations[n - mid] >= mid) { left = mid; } else { right = mid - 1; } } return left; }}class Solution {public: int hIndex(vector<int> &citations) { int n = citations.size(); int left = 0, right = n; while (left < right) { int mid = (left + right + 1) >> 1; if (citations[n - mid] >= mid) left = mid; else right = mid - 1; } return left; }};class Solution : def hIndex ( self , citations : List [ int ]) -> int : n = len ( citations ) left , right = 0 , n while left < right : mid = ( left + right + 1 ) >> 1 if citations [ n - mid ] >= mid : left = mid else : right = mid - 1 return leftVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.