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
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; }}Video 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.