H-Index II

Problem

Given citations sorted ascending, return the h-index — the max h with at least h papers each cited ≥ h times. O(log n).

Constraints

• 0 ≤ citations.length ≤ 10⁵

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

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

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.