H-Index II

H-Index II

What is this problem about?

The H-Index II interview question is a variation of the classic H-Index problem where you are given an array of citations sorted in ascending order. The H-Index is a metric that measures both the productivity and citation impact of a researcher. Specifically, a researcher has an index $h$ if $h$ of their $n$ papers have at least $h$ citations each, and the other $n - h$ papers have no more than $h$ citations each. In this problem, the primary goal is to find the maximum possible value of $h$ efficiently, leveraging the fact that the input array is already sorted.

Why is this asked in interviews?

Companies like Meta and Amazon ask the H-Index II coding problem to test a candidate's ability to optimize a linear search into a logarithmic one. Since the array is sorted, a linear scan ($O(n)$) is possible but not optimal. The core challenge is recognizing that the sorted property allows for the use of the binary search interview pattern. It evaluations whether you can correctly identify the search space and the conditions for moving the left and right pointers in a non-standard search scenario.

Algorithmic pattern used

The primary algorithmic pattern used is Binary Search. The search range is the indices of the array $[0, n-1]$. For any index mid, the number of papers with at least citations[mid] citations is n - mid. We are looking for the smallest index mid such that citations[mid] >= n - mid. This point represents the boundary where the H-Index condition is met.

Example explanation

Imagine a researcher has 5 papers with citations: [0, 1, 3, 5, 6].

1. Start: low = 0, high = 4.
2. Mid = 2: Value is 3. Number of papers from this point to the end is $5 - 2 = 3$.
3. Check: Since $3 \ge 3$, this is a valid $h$, but we want to see if a larger $h$ exists (which means a smaller index). We move high = 1.
4. Wait, the logic for finding the maximum $h$ involves finding the largest $n-mid$. In this case, at index 2, $h = 3$ is achievable. If we checked index 1, value is 1, $n-1=4$. $1 < 4$, so not valid. The result is 3.

Common mistakes candidates make

• Linear Scan: Using a simple loop to find the H-Index, which results in $O(n)$ complexity and misses the point of the problem.
• Index Confusion: Miscalculating the number of papers as mid or mid + 1 instead of n - mid.
• Boundary Conditions: Getting the binary search termination condition wrong, leading to off-by-one errors in the final result.

Interview preparation tip

When you see "Sorted Array" and "Find an optimal value," always think Binary Search. Practice explaining the relationship between the index and the value in this specific context, as the "target" isn't a fixed number but a dynamic condition based on the number of elements remaining.