Problem Description

You are given an array citations where citations[i] represents the number of citations a researcher received for their i-th paper. The array is sorted in non-descending order (ascending order).

Your task is to find the researcher's h-index.

The h-index is defined as the maximum value of h such that the researcher has published at least h papers that have each been cited at least h times.

For example:

• If a researcher has 5 papers with citations [0, 1, 3, 5, 6], their h-index is 3 because:
  • They have 3 papers with at least 3 citations each (papers with 3, 5, and 6 citations)
  • They don't have 4 papers with at least 4 citations each

The key insight for the binary search approach is that we're looking for the maximum h where at least h papers have h or more citations. Since the array is sorted, if we want to check if there are at least mid papers with at least mid citations, we need to verify that citations[n - mid] >= mid. This works because:

• The last mid papers in the sorted array are from index n - mid to n - 1
• If citations[n - mid] >= mid, then all papers from index n - mid onwards have at least mid citations
• This means we have at least mid papers with at least mid citations

The algorithm must run in logarithmic time complexity, which suggests using binary search to find the optimal h-index value.

Intuition

The key observation is that the h-index has a monotonic property. If a researcher has an h-index of x, it means they have at least x papers with x or more citations. This automatically implies they also have at least y papers with y or more citations for any y < x.

Think of it this way: if you have 5 papers with at least 5 citations each, you definitely also have 4 papers with at least 4 citations each, 3 papers with at least 3 citations each, and so on.

This monotonic property suggests we can use binary search. We're essentially searching for the maximum value of h where the condition "at least h papers have h or more citations" is still true.

Since the array is sorted in ascending order, checking if we have at least h papers with h or more citations becomes straightforward:

• The papers with the highest citations are at the end of the array
• If we want h papers with at least h citations, we look at the last h papers
• The last h papers start from index n - h
• The minimum citation among these last h papers is citations[n - h]
• So we need citations[n - h] >= h

The binary search works by:

1. Starting with a search range from 0 to n (the maximum possible h-index is n)
2. Checking the middle value mid to see if it's a valid h-index
3. If citations[n - mid] >= mid, it means mid is a valid h-index, but there might be a larger one, so we search the right half
4. Otherwise, mid is too large to be an h-index, so we search the left half
5. We continue until we find the maximum valid h-index

Solution Approach

We implement a binary search algorithm to find the maximum h-index value. The search space is from 0 to n (the length of the citations array), as the h-index cannot exceed the total number of papers.

The implementation follows these steps:

1. Initialize search boundaries: Set left = 0 and right = n, where n is the length of the citations array.

2. Binary search loop: While left < right:

   • Calculate the midpoint: mid = (left + right + 1) >> 1
     • The >> 1 operation is a bitwise right shift, equivalent to dividing by 2
     • We use (left + right + 1) instead of (left + right) to ensure the search converges correctly when searching for the maximum value

3. Check validity condition: For each mid value, we check if it's a valid h-index:

   • We need at least mid papers with at least mid citations
   • Since the array is sorted, the last mid papers have the highest citations
   • These papers start from index n - mid
   • If citations[n - mid] >= mid, then all papers from index n - mid to n - 1 have at least mid citations

4. Update search boundaries:

   • If citations[n - mid] >= mid: This means mid is a valid h-index, but there might be a larger one. Update left = mid to search for larger values
   • Otherwise: mid is too large to be a valid h-index. Update right = mid - 1 to search for smaller values

5. Return result: When the loop ends, left contains the maximum h-index value.

The algorithm achieves O(log n) time complexity through binary search, meeting the problem's requirement for logarithmic time. The space complexity is O(1) as we only use a constant amount of extra space for the pointers.

Example Walkthrough

Let's walk through the solution with a concrete example: citations = [0, 1, 3, 5, 6]

We need to find the maximum h-index where at least h papers have h or more citations.

Initial Setup:

• Array length n = 5
• Search range: left = 0, right = 5

Iteration 1:

• Calculate mid = (0 + 5 + 1) >> 1 = 3
• Check if h-index of 3 is valid:
  • We need at least 3 papers with at least 3 citations
  • The last 3 papers start at index n - mid = 5 - 3 = 2
  • Check citations[2] >= 3: Is 3 >= 3? Yes!
  • This means papers at indices 2, 3, 4 (with citations 3, 5, 6) all have at least 3 citations
• Since valid, search for larger h-index: left = 3, right = 5

Iteration 2:

• Calculate mid = (3 + 5 + 1) >> 1 = 4
• Check if h-index of 4 is valid:
  • We need at least 4 papers with at least 4 citations
  • The last 4 papers start at index n - mid = 5 - 4 = 1
  • Check citations[1] >= 4: Is 1 >= 4? No!
  • The paper at index 1 only has 1 citation, which is less than 4
• Since invalid, search for smaller h-index: left = 3, right = 3

Termination:

• left == right, so we exit the loop
• Return left = 3

Verification: The h-index is 3 because:

• Papers with citations [3, 5, 6] (3 papers) each have at least 3 citations ✓
• We cannot have h-index of 4 because we don't have 4 papers with at least 4 citations ✗

The binary search efficiently found the maximum h-index in just 2 iterations instead of checking all possible values from 0 to 5.

Solution Implementation

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. Incorrect Midpoint Calculation in Binary Search

Pitfall: Using mid = (left + right) // 2 instead of mid = (left + right + 1) // 2 when searching for the maximum value.

When searching for the maximum valid h-index, if we use the standard midpoint calculation, the binary search can get stuck in an infinite loop. Consider when left = 4 and right = 5:

• With mid = (4 + 5) // 2 = 4, if the condition is satisfied, we set left = mid = 4, resulting in no progress
• The loop continues indefinitely with the same values

Solution: Use mid = (left + right + 1) // 2 to bias toward the right when the range has even length. This ensures the search space always decreases:

mid = (left + right + 1) // 2  # Correct for finding maximum

2. Array Index Out of Bounds

Pitfall: Not handling edge cases where mid = 0 or mid = n, leading to invalid array access at citations[n - mid].

When mid = 0, we're checking if there are at least 0 papers with 0+ citations (always true for non-empty arrays). When mid = n, we check citations[0], which might cause confusion about what we're actually validating.

Solution: Add boundary checks or handle the edge cases explicitly:

if mid == 0:
    return 0  # h-index of 0 is always valid
if mid > 0 and citations[n - mid] >= mid:
    left = mid

3. Misunderstanding the Condition Check

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

Some might incorrectly think about checking from the beginning of the array. The confusion arises from trying to check "if the paper at position mid has enough citations for the remaining papers."

Solution: Remember that we need the last mid papers (highest citations) to each have at least mid citations:

# Correct: Check if the (n-mid)th paper has at least mid citations
if citations[n - mid] >= mid:
    # We have at least mid papers with >= mid citations

4. Off-by-One Error in Search Range

Pitfall: Initializing right = n - 1 instead of right = n.

The h-index can be equal to the total number of papers n. For example, if all 5 papers have 5+ citations each, the h-index is 5. Setting right = n - 1 would miss this valid case.

Solution: Initialize the search range correctly:

left, right = 0, n  # Include n as a possible h-index value