H-Index II — Binary Search on Sorted Citations [LC 275]

Problem Statement#

LeetCode 275 — H-Index II · Difficulty: Medium

Given an array citations of integers sorted in non-decreasing order, where citations[i] is the number of citations a researcher received for their i-th paper, return the researcher's h-index.

The h-index is defined as the maximum value h such that the researcher has published at least h papers with at least h citations each.

Constraints:

• n == citations.length
• 1 <= n <= 10^5
• 0 <= citations[i] <= 1000
• citations is sorted in non-decreasing order

Example 1:

Input:  citations = [0, 1, 3, 5, 6]
Output: 3
Explanation: There are 5 papers. 3 papers have at least 3 citations each (citations[2]=3, [3]=5, [4]=6).
             But NOT 4 papers have at least 4 citations (only 2 papers have >= 4).
             So h-index = 3.

Example 2:

Input:  citations = [1, 2, 100]
Output: 2
Explanation: 2 papers have at least 2 citations ([1]=2, [2]=100). 
             3 papers do NOT all have >= 3 citations (citations[0]=1 < 3). So h = 2.

Example 3:

Input:  citations = [0, 0, 0]
Output: 0
Explanation: No paper has any citations. h-index = 0.

Why This Problem Matters#

H-Index II is a masterclass in translating a real-world metric into a binary search condition. The array is sorted, so there must be a binary search solution — but the condition is non-obvious. This is exactly what Google and Meta interviewers look for: can you derive the search condition yourself, rather than just applying a memorised template?

LC 274 (H-Index) solves the unsorted version in O(n log n) by sorting first. LC 275 (this problem) asks for O(log n) on the already-sorted array. The jump from O(n log n) to O(log n) requires recognising a monotone structure and expressing the h-index condition in terms of array indices — a skill that separates strong binary search practitioners from average ones.

The Core Insight#

With n papers sorted in non-decreasing order by citations, if we pick index mid, then exactly n - mid papers have citations >= citations[mid] (all papers from index mid to n-1).

We want the smallest index mid such that citations[mid] >= n - mid.

Why? Because at that index, there are n - mid papers with at least n - mid citations. The h-index is then n - mid — the number of papers in the qualifying group.

The monotone property: once citations[mid] >= n - mid is true at some index, it remains true for all larger indices. So we can binary search for the leftmost index where this condition holds.

Boundary cases:

• If no index satisfies the condition (all citations are 0), lo ends at n, and n - lo = 0 — correct h-index of 0.
• If all papers have high citations, lo ends at 0, and n - 0 = n — every paper qualifies.

Visual Dry Run#

Input: citations = [0, 1, 3, 5, 6], n = 5

We seek the smallest mid where citations[mid] >= n - mid = 5 - mid.

Leftmost Yes is at index 2. h-index = n - 2 = 3. Correct.

Binary search trace:

Input: citations = [1, 2, 100], n = 3

Common Mistakes#

1. Binary searching on the h-value instead of the index — it is tempting to binary search on the value h from 0 to n. This works but requires a linear scan per check (O(n log n) total). The O(log n) solution searches on the index directly.

2. Using hi = n - 1 instead of hi = n — the h-index could be 0, meaning lo should reach n (past the last index). Initialising hi = n - 1 prevents this and incorrectly returns a positive h-index even when citations are all 0.

3. Confusing the condition direction — the condition citations[mid] >= n - mid must hold to move hi left (we want the leftmost Yes). Reversing to citations[mid] < n - mid → lo = mid + 1 is the else branch. Getting these backwards finds the wrong boundary.

4. Not understanding what n - lo represents — after the search, lo is the first index where the condition holds. n - lo counts papers from lo to n-1, each having >= n - lo citations. This is the h-index by definition.

5. Forgetting the all-zeros edge case — citations = [0, 0, 0] should return 0. With hi = n, the loop runs correctly and lo ends at n, giving n - n = 0.

6. Mishandling ties in citations — if multiple papers have the same citation count, the leftmost-boundary search correctly finds the first position where the group is large enough.

7. Off-by-one when computing n - mid — n - mid counts elements from index mid inclusive to the end. Double-check: for n = 5 and mid = 2, that is indices 2, 3, 4 → 3 papers. 5 - 2 = 3. Correct.

Solutions#

Python#

def hIndex(citations: list[int]) -> int:
    n = len(citations)
    # Search for the leftmost index where citations[mid] >= n - mid.
    # lo ranges over [0, n]; hi = n allows the result n - lo = 0.
    lo, hi = 0, n
 
    while lo < hi:
        mid = lo + (hi - lo) // 2          # lower-mid for left-boundary search
 
        # At index mid, there are (n - mid) papers with >= citations[mid] citations.
        # If this count is at most citations[mid], this index qualifies.
        if citations[mid] >= n - mid:
            hi = mid                        # condition met: try to go further left
        else:
            lo = mid + 1                   # condition not met: first valid index is to the right
 
    # lo is the first qualifying index. n - lo papers form the h-index group.
    return n - lo

JavaScript#

function hIndex(citations) {
    const n = citations.length;
    // hi = n (not n-1) to handle the case where h-index is 0
    let lo = 0, hi = n;
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2); // lower-mid for left-boundary
 
        // n - mid papers exist from index mid to n-1.
        // If citations[mid] >= n - mid, all those papers qualify.
        if (citations[mid] >= n - mid) {
            hi = mid;               // valid: search left for an even earlier qualifying index
        } else {
            lo = mid + 1;           // not valid: first qualifying index must be to the right
        }
    }
 
    // lo is the leftmost qualifying index; n - lo is the h-index
    return n - lo;
}

Complexity Analysis#

The binary search runs at most ceil(log₂(n+1)) iterations. For n = 10^5, that is at most 17 comparisons. Each comparison is O(1). Total time: O(log n).

Follow-up Questions#

1. How does LC 274 differ? — LC 274 gives an unsorted array. You sort it first in O(n log n), then apply this same binary search. The sorted structure is what enables O(log n).

2. Why is hi initialised to n and not n-1? — The h-index can be 0 (no qualifying papers). When lo reaches n, n - lo = 0 correctly returns 0. With hi = n-1, you can never reach this state.

3. Can there be multiple valid h-index values? — By definition, the h-index is unique — it is the maximum h satisfying the condition. The binary search finds it exactly.

4. What if all citations are the same value, say c? — All n papers have c citations. The h-index is min(c, n). Binary search converges to index 0 if c >= n (h = n), or to some positive index otherwise.

5. How would you modify this for descending-sorted citations? — Adjust the condition: at index mid, there are mid + 1 papers (from 0 to mid). Condition becomes citations[mid] >= mid + 1. Find the rightmost index where this holds.

This Pattern Solves#

• LC 275 — H-Index II (this problem)
• LC 274 — H-Index (sort first, then same binary search)
• LC 35 — Search Insert Position (left-boundary: find where value belongs)
• LC 34 — Find First and Last Position (dual left/right boundary search)
• LC 278 — First Bad Version (left-boundary on a boolean predicate)
• Any problem where you need to find the leftmost index satisfying a monotone condition

Key Takeaway#

H-Index II teaches a crucial binary search skill: translating a real-world optimisation condition into a binary comparison on indices. The key observation is that n - mid papers lie at or after index mid, so the condition citations[mid] >= n - mid tells us the qualifying group starts no later than mid. Binary search on this condition with left-boundary template (hi = mid on success) finds the answer in O(log n). Initialise hi = n (not n-1) to correctly handle the zero h-index case.

Key Takeaways#

• LC 275 (H-Index II) converts a real-world academic metric into a left-boundary binary search; it tests index-arithmetic reasoning rather than algorithmic templates.
• The key observation: at any index mid in a sorted citations array, there are exactly n - mid papers with citations >= citations[mid], since the array is ascending.
• The binary condition citations[mid] >= n - mid is true when index mid or earlier can anchor the h-index — search for the leftmost such index.
• Use hi = n (not n - 1) to allow lo to settle at n when no paper qualifies, giving n - n = 0 as the correct h-index.
• The answer is n - lo after the loop: the number of papers in the qualifying group starting at the leftmost valid index.
• LC 274 (H-Index, unsorted version) requires sorting first in O(n log n) then applies this same binary search — LC 275 skips the sort.
• The left-boundary template (hi = mid on success, lo = mid + 1 on failure) finds the earliest qualifying index in O(log n).