Domain 2MediumCORE

H-Index II

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: $h$ papers have at least $h$ citations, and the remaining $n-h$ papers have no more than $h$.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Binary Search

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: hh papers have at least hh citations, and the remaining n−hn-h papers have no more than hh.

Key Inputs:

  • Sorted array citations (ascending).
  • Length of array n=105n = 10^5.
  • 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 (O(log⁡n)O(\log n)).
  • Empty Input: While constraints say n≥1n \ge 1, 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 (nn). If all citations are very high, h=nh=n.

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 hh, checking linearly is inefficient (O(n)O(n)) 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