Watch 10 video solutions for H-Index II, a medium level problem involving Array, Binary Search. This walkthrough by Techdose has 53,608 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given a sorted array citations where citations[i] represents how many times a research paper has been cited. The array is sorted in ascending order. The goal is to compute the researcher's H-index, defined as the maximum h such that the researcher has at least h papers with h or more citations.
The sorted property changes how you approach the problem compared to the original H-Index problem. Instead of scanning all counts or sorting, you can exploit ordering to locate the correct boundary where the number of remaining papers matches the citation requirement.
Approach 1: Linear Scan Approach (O(n) time, O(1) space)
Because the array is sorted, you can iterate from the beginning and check the number of papers remaining at each index. If you are at index i, then there are n - i papers with at least citations[i] citations. The H-index condition becomes citations[i] >= n - i. The first position where this holds gives the answer n - i. This approach performs a single pass through the array, making it simple to implement while still using constant memory. Although the runtime is linear, the logic clearly expresses the definition of H-index and works well when input sizes are moderate.
Approach 2: Binary Search Approach (O(log n) time, O(1) space)
The sorted property allows a faster solution using binary search. Instead of checking every index, search for the smallest index i where citations[i] >= n - i. This condition represents the transition point where the citation count becomes large enough to satisfy the H-index definition. During each step, compute mid and compare citations[mid] with n - mid. If the citation value is large enough, move left to find an earlier valid index; otherwise move right. Once the search ends, the H-index is n - left. This approach reduces the search space by half each iteration and is the expected optimal solution when the input is already sorted.
Recommended for interviews: Interviewers usually expect the binary search solution because the problem explicitly guarantees a sorted array. A linear scan demonstrates you understand the H-index definition, but the binary search approach shows that you recognize the monotonic property and can convert it into a logarithmic-time algorithm.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Simple implementation when performance constraints are moderate |
| Binary Search | O(log n) | O(1) | Best choice when the citations array is sorted and large |