H-Index II — Binary Search on Sorted Citations

Problem 330 · H-Index II

Difficulty: Medium · Pattern: Left Boundary

Citations sorted. Find h such that there are at least h papers with >= h citations.

Intuition

For index mid, n-mid papers have citations >= citations[mid]. Find smallest mid where citations[mid] >= n-mid.

Solutions

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

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

Complexity

Time: O(log n)
Space: O(1)