Problem Description

The H-Index II problem on LeetCode asks you to compute the researcher's h-index given a sorted (ascending) array of citation counts for their papers. The h-index is defined as the maximum value h such that the given researcher has published at least h papers that have each been cited at least h times.

• The input is a sorted list of non-negative integers citations, where citations[i] is the number of citations for the ith paper.
• You must find the researcher's h-index using this list.
• Key constraints: The array is sorted in ascending order. Your algorithm should run in logarithmic time (O(log n)), which strongly hints at using binary search.
• The problem guarantees that there is only one valid answer.

Thought Process

To solve this problem, let's first understand what the h-index represents: it's the largest number h such that at least h papers have at least h citations each.

The brute-force approach would be to check, for every possible h from 0 up to n (the total number of papers), whether there are at least h papers with at least h citations. However, since the input array is sorted, we can do better.

The sorted order allows us to use binary search to efficiently find the point where the number of papers with citations greater than or equal to a certain value matches that value. The trick is to recognize that for each index i in the array, the number of papers with at least citations[i] citations is n - i.

We want to find the smallest index i where citations[i] >= n - i. Then, the answer is n - i.

Solution Approach

• Step 1: Recognize that the array is sorted in ascending order. This allows for binary search.
• Step 2: For each index i, the number of papers with at least citations[i] citations is n - i.
• Step 3: Use binary search to find the smallest index i where citations[i] >= n - i.
• Step 4: Once found, h-index is n - i. If no such i exists, the h-index is 0.
• Why binary search? Because at each iteration, we can check the mid-point and decide whether to search the left or right half based on whether citations[mid] >= n - mid.
• Edge cases: If all papers have 0 citations, the answer is 0. If all have very high citations, the answer is n.

Example Walkthrough

Consider the input citations = [0, 1, 3, 5, 6].

• Step 1: n = 5
• Step 2: We want to find the smallest i where citations[i] >= n - i.
• Binary Search Iterations:
  • First, left = 0, right = 4. mid = 2. citations[2] = 3, n - mid = 3. 3 >= 3 (true). Move right to mid - 1 = 1.
  • Now, left = 0, right = 1. mid = 0. citations[0] = 0, n - mid = 5. 0 < 5 (false). Move left to mid + 1 = 1.
  • Now, left = 1, right = 1. mid = 1. citations[1] = 1, n - mid = 4. 1 < 4 (false). Move left to mid + 1 = 2.
• Now, left = 2, which is our answer. h-index = n - left = 5 - 2 = 3.
• So, the researcher has 3 papers with at least 3 citations each.

Time and Space Complexity

• Brute-force approach:
  • For each possible h from 0 to n, count how many papers have at least h citations. This is O(n^2) in the worst case.
• Optimized (binary search) approach:
  • Binary search takes O(log n) time.
  • Each check is O(1) because we use array indices and simple arithmetic.
  • Space complexity is O(1) since we only use a few variables for indices.

Code Implementation

class Solution:
    def hIndex(self, citations):
        n = len(citations)
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if citations[mid] >= n - mid:
                right = mid - 1
            else:
                left = mid + 1
        return n - left
      

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return n - left;
    }
};
      

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return n - left;
    }
}
      

var hIndex = function(citations) {
    let n = citations.length;
    let left = 0, right = n - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (citations[mid] >= n - mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return n - left;
};
      

Summary

The H-Index II problem leverages the sorted property of the input array to allow a binary search solution, reducing the time complexity from O(n^2) (brute-force) to O(log n). By understanding the relationship between array indices and the number of papers with at least a certain number of citations, we can efficiently compute the h-index in a way that's both optimal and elegant.