H-Index II - Solution & Explanation

Problem Overview: You receive a sorted array citations where citations[i] represents the number of citations for a research paper. The array is sorted in ascending order. Your goal is to compute the researcher's H-index: the maximum h such that at least h papers have ≥ h citations.

The sorted property changes how you approach the problem compared to the original H-Index problem. Instead of scanning all possible values, you can use the index position to infer how many papers remain on the right side of the array.

Approach 1: Linear Scan from the End (O(n) time, O(1) space)

Start from the end of the sorted array where citation counts are largest. For each index i, the number of papers with at least citations[i] citations equals n - i. Check whether citations[i] >= n - i. The first position that satisfies this condition determines the H-index.

This works because the array is sorted: moving left only decreases citation counts while increasing the number of papers considered. Once the condition becomes true, you’ve found the largest valid H-index. The algorithm simply iterates once across the array, making it easy to implement with constant memory.

This approach is practical when input size is moderate or when code simplicity matters more than theoretical optimality. It relies only on sequential iteration over an array.

Approach 2: Binary Search on Citation Threshold (O(log n) time, O(1) space)

The sorted order enables a classic binary search. Instead of checking every index, search for the smallest index i where citations[i] >= n - i. The value n - i represents how many papers lie to the right (including the current one), which corresponds to a potential H-index candidate.

During the search, compute mid. If citations[mid] >= n - mid, the condition might hold for an even smaller index, so move the right boundary left. Otherwise, move the left boundary right because the citation count is too small to support that many papers.

Once the search converges, the H-index equals n - left. This reduces the complexity from linear to logarithmic time while maintaining constant memory usage. Binary search fits naturally because the condition forms a monotonic boundary across the sorted array.

This solution combines array indexing with binary search logic and is the expected optimal approach in most technical interviews.

Recommended for interviews: Start by explaining the linear scan to demonstrate understanding of the H-index definition. Then optimize using binary search by leveraging the sorted array property. Interviewers typically expect the O(log n) binary search solution because recognizing the monotonic condition shows strong algorithmic reasoning.