Solution Approach

We use the standard binary search template to find the h-index. The key insight is to define a feasible function that creates a false, false, ..., true, true pattern.

Feasible Function: We define feasible(index) as: at position index, does citations[index] >= n - index?

This checks if the paper at position index has enough citations to contribute to an h-index of n - index. When this becomes true, all papers from this position onwards contribute to the h-index.

Template Implementation:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):  # citations[mid] >= n - mid
        first_true_index = mid
        right = mid - 1  # search for earlier true position
    else:
        left = mid + 1

return n - first_true_index if first_true_index != -1 else 0

How it works:

1. Initialize left = 0, right = n - 1, and first_true_index = -1
2. Use while left <= right loop (NOT left < right)
3. Check if citations[mid] >= n - mid (feasible condition)
4. If true, record first_true_index = mid and search left with right = mid - 1
5. If false, search right with left = mid + 1
6. The h-index is n - first_true_index

The algorithm achieves O(log n) time complexity and O(1) space complexity.

Example Walkthrough

Let's walk through the solution with citations = [0, 1, 3, 5, 6] using the binary search template.

Initial Setup:

• Array length n = 5
• left = 0, right = 4 (n - 1)
• first_true_index = -1
• Feasible condition: citations[mid] >= n - mid

Iteration 1:

• left = 0, right = 4
• mid = (0 + 4) // 2 = 2
• Check citations[2] >= 5 - 2: Is 3 >= 3? Yes! (feasible)
• Update: first_true_index = 2, right = mid - 1 = 1

Iteration 2:

• left = 0, right = 1
• mid = (0 + 1) // 2 = 0
• Check citations[0] >= 5 - 0: Is 0 >= 5? No! (not feasible)
• Update: left = mid + 1 = 1

Iteration 3:

• left = 1, right = 1
• mid = (1 + 1) // 2 = 1
• Check citations[1] >= 5 - 1: Is 1 >= 4? No! (not feasible)
• Update: left = mid + 1 = 2

Termination:

• left = 2 > right = 1, exit loop
• first_true_index = 2
• h-index = n - first_true_index = 5 - 2 = 3

Verification:

• Position 2 is the first where citations[index] >= n - index
• From index 2 onwards: papers with 3, 5, 6 citations all meet the threshold
• h-index = 3 means 3 papers have at least 3 citations each ✓

Time and Space Complexity

The time complexity is O(log n), where n is the length of the array citations. This is because the algorithm uses binary search to find the h-index. In each iteration of the while loop, the search space is reduced by half (either left = mid or right = mid - 1), resulting in at most log n iterations.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables n, left, right, and mid, regardless of the input size. No additional data structures that scale with the input are created.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

Pitfall: Using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

# WRONG - different template variant
while left < right:
    mid = (left + right) // 2
    if citations[mid] >= n - mid:
        right = mid
    else:
        left = mid + 1
return n - left

Solution: Use the standard binary search template with first_true_index:

# CORRECT - standard template
left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if citations[mid] >= n - mid:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return n - first_true_index if first_true_index != -1 else 0

2. Not Handling Empty Array

Pitfall: Accessing citations[mid] when the array is empty causes an index error.

Solution: Add an early return for empty arrays:

if n == 0:
    return 0

3. Confusing the Feasible Condition

Pitfall: Using citations[mid] >= mid instead of citations[mid] >= n - mid.

The condition checks if the paper at position mid contributes to an h-index. The h-index from position mid onwards is n - mid papers, so the citation count must be at least n - mid.

Solution: Remember the feasible condition clearly:

# citations[mid] >= n - mid means:
# "Paper at mid has enough citations for an h-index of (n - mid)"

4. Forgetting to Handle first_true_index == -1

Pitfall: When no position satisfies the feasible condition (all papers have 0 citations), first_true_index remains -1 and the formula n - first_true_index gives wrong result.

Solution: Check for the not-found case:

return n - first_true_index if first_true_index != -1 else 0