Get started

H-Index II — Medium Problem & Solution

citations[i] is the number of citations the researcher's i-th paper received, sorted in ascending order.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

citations[i] is the number of citations the researcher's i-th paper received, sorted in ascending order.

The h-index is the largest h such that at least h papers have at least h citations each. Return it in O(log n) time.

Example 1

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: Three papers have at least 3 citations.

Example 2

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

Example 3

Input: citations = [0]
Output: 0

Constraints

  • 1 <= citations.length <= 100000
  • 0 <= citations[i] <= 1000
  • citations is sorted in ascending order.

How to solve H-Index II

With the array sorted ascending, the h most-cited papers are its last h entries, and the weakest of them sits at index n - h. So the test is a single array lookup, and it is monotone in h.

Approach

  1. Binary search h over [0, n].
  2. For a candidate count mid (meaning h = mid + 1), check citations[n - 1 - mid] >= mid + 1.
  3. Move lo past mid when it holds; the final lo is the h-index.

Why it works

If h papers each have at least h citations, then h - 1 papers each have at least h - 1 — so feasibility is downward closed and the boundary is unique. Sorting means the weakest of the top h is citations[n - h], which makes the check O(1) and the whole search logarithmic.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Off-by-one between h and the array index is the classic trap — h papers means indices n - h … n - 1.
  • Sorting or counting would be O(n log n) or O(n), both failing the stated requirement.
  • An h-index of 0 is legitimate when the best paper has no citations.

Reference solution

Python

from typing import List

def hIndex(citations: List[int]) -> int:
    n = len(citations)
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if citations[n - 1 - mid] >= mid + 1:
            lo = mid + 1
        else:
            hi = mid
    return lo

JavaScript

var hIndex = function(citations) {
    var n = citations.length;
    var lo = 0, hi = n;
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (citations[n - 1 - mid] >= mid + 1) lo = mid + 1; else hi = mid;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue