Skip to main content

275. H-Index II

medium

Compute a researcher's h-index from a citation array that's already sorted. The sorted input is a hint, not a coincidence — binary search to O(log n).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index. The h-index is defined as the maximum value h such that the researcher has published at least h papers that have each been cited at least h times. The citations array is sorted in ascending order. You must write an algorithm that runs in O(log n) time.

Constraints

  • n == citations.length
  • 1 <= n <= 10^5
  • 0 <= citations[i] <= 1000
  • citations is sorted in ascending order.

Examples

Example 1

Input
citations = [0,1,3,5,6]
Output
3

Explanation: The researcher has 3 papers with at least 3 citations each (3, 5, 6), and the remaining two have no more than 3 citations each.

Example 2

Input
citations = [1,2,100]
Output
2

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If citations is sorted ascending, then for any index i there are exactly n - i papers with citations[i] or more citations.

Hint 2

You want the largest h such that there exists an index i where citations[i] >= n - i and n - i >= h. Equivalently: find the leftmost i where citations[i] >= n - i; the answer is n - i.

Hint 3

Binary-search the predicate P(i) := citations[i] >= n - i. P is monotonic — once true, it stays true.

Solution approach

Reveal approach

Binary search the leftmost index i where citations[i] >= n - i. The intuition: at index i, there are n - i papers from position i onward, each with at least citations[i] citations. If citations[i] >= n - i, then h = n - i works. The predicate P(i) := citations[i] >= n - i is monotonic in i (citations[i] is non-decreasing while n - i strictly decreases), so we can binary-search for the leftmost true. Initialize lo = 0 and hi = n. While lo < hi, mid = lo + (hi - lo) / 2; if citations[mid] >= n - mid, hi = mid; else lo = mid + 1. Return n - lo. When lo reaches n (no valid index), n - lo = 0, which is the correct h-index for arrays of all zeros. O(log n) time, O(1) space — exactly what the problem demands.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • modified-binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Bloomberg
  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill H-Index II and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →