H-Index II — Editorial

Opening the reading…

Intuitionthe h-index becomes a boundary in the sorted array

Suppose you choose a paper at index i as the first paper counted toward the h-index. There are n - i papers from i through the end, and because citations is sorted, every one of them has at least citations[i] citations. This suffix supports an h-index of n - i exactly when citations[i] >= n - i.

As i moves right, citations[i] never decreases while n - i decreases. Therefore the condition citations[i] >= n - i can change only once: it is false for a prefix and true for the remaining suffix. The answer comes from the first true index left, because that index leaves the largest qualifying suffix, so the h-index is n - left. If no index is true, left becomes n and the answer is zero.

Approachsearch for the first index whose suffix is large enough

Set left to 0 and right to n - 1, because every possible first qualifying paper must be inside the array and an empty qualifying suffix is handled when left reaches n.

Choose mid between left and right without adding the two endpoints directly, because left + right can overflow in a general binary-search implementation.

Check whether citations[mid] >= n - mid. This asks whether the suffix beginning at mid contains enough papers, each with enough citations, to support its own size as the h-index.

If the condition is true, move right to mid - 1, because mid already qualifies but an earlier index may also qualify and would produce a larger h-index.

If the condition is false, move left to mid + 1, because mid and every earlier index fail: earlier indices have no more citations and demand a suffix at least as large.

When the loop ends, left is the first qualifying index, so return n - left. Returning the suffix length rather than citations[left] matters because the h-index is limited by the number of qualifying papers.

Complexitythe search keeps only a constant amount of state

MEASURE	BOUND	WHY
Time	O(log n)	Each comparison discards either the left half or the right half of the remaining index interval. The interval therefore shrinks by about half per iteration, and no index is scanned separately.
Space	O(1) extra	The algorithm stores only n, left, right, and mid; the returned h-index is a single integer and is output rather than working memory. The bound stays constant even for the worst citation distribution, including all zeros or all very large values.

Annotated solutionC++ · lower-bound binary search on the first valid index

CPPBinary-search the first index i where citations[i] is at least the suffix length n - i.

#include <vector>

using namespace std;

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0;
        int right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return n - left;
    }
};

The important placement is the true branch: a qualifying mid is not the answer yet, because an earlier index may qualify and produce a larger suffix. Moving right leftward preserves mid as a possible boundary while searching for the first true position. After the loop, left is either that boundary or n when no paper qualifies, and n - left handles both cases without a special final scan.