H-Index II

Medium
822.

H-Index II

H-Index II is a medium coding problem on arrays and binary search, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

H-Index II — Solution in Python, Java & C++

H-Index II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

H-Index II is a medium coding problem on arrays and binary search, asked in Amazon, Google and Adobe interviews.

  • 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.

Hints for H-Index II

  1. Hint 1

    Counting from the top: the h most-cited papers are the last h of the sorted array.

  2. Hint 2

    So h works exactly when citations[n - h] >= h.

  3. Hint 3

    That predicate is monotone in h, so binary search it.

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

Java

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

C++

int hIndex(vector<int>& citations) {
    int n = (int) citations.size();
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search