275. H-Index II
Model: qwen3.5:9b
Topics: Binary Search
FAANG asked: 0
Acceptance rate: 36.4%
Problem Breakdown
We are given a sorted array of integers citations, where each integer represents citations received by one paper in ascending order. We need to compute the researcher’s h-index based on the definition: papers have at least citations, and the remaining papers have no more than .
Key Inputs:
- Sorted array
citations(ascending). - Length of array .
- Citation values are non-negative.
Outputs:
- An integer representing the maximum valid h-index.
Implicit Constraints & Edge Cases:
- Sorted Property: The input is sorted in ascending order, which allows us to use Binary Search instead of a linear scan. This satisfies the follow-up requirement for logarithmic time complexity ().
- Empty Input: While constraints say , robust code should handle empty arrays (returning 0) if this were possible in production, though here we assume valid input per constraints.
- Max H-Index Bound: The h-index cannot exceed the number of papers (). If all citations are very high, .
Intuition
The brute-force approach would be to iterate through every paper and check if it satisfies the condition for a specific h-index value. However, since we want the maximum possible , checking linearly is inefficient () given the follow-up constraint asks for logarithmic time.
Key Insight:
In a sorted array citations, consider an index i (0-based). There are exactly (n - i) papers from this index to the end of the array, including itself. Since the array is sorted ascendingly, all these papers have at least citations[i] citations.
Therefore, if we find a paper at index i where:
citations[i] >= n - i
It means there are (n - i) papers with at least that many citations. This makes (n - i) a valid candidate for the