Solution Explanation for LeetCode 275: H-Index II

This problem asks to find the h-index of a researcher given a sorted array of citation counts for their papers. The h-index is the largest number h such that the researcher has at least h papers with at least h citations each. Since the input array citations is sorted in ascending order, we can leverage this property to design an efficient algorithm using binary search.

Understanding the Logic

The key observation is the monotonic nature of the problem. If a researcher has at least x papers with at least x citations, then it's guaranteed that they also have at least y papers with at least y citations for any y < x. This allows us to efficiently search for the maximum h using binary search.

Algorithm (Binary Search)

1. Initialization: Set left to 0 and right to the length of citations (n). This defines the search space for the h-index.

2. Iteration: While left is less than right:

   • Calculate the middle index mid = (left + right + 1) // 2 (integer division). The +1 ensures we lean towards a higher mid to find the maximum h-index.
   • Check the condition citations[n - mid] >= mid. This checks if there are at least mid papers with at least mid citations.
     • If the condition is true, it means we might find a larger h-index, so we update left = mid.
     • Otherwise, the current mid is too high, so we update right = mid - 1.

3. Result: After the loop terminates, left holds the maximum value of h that satisfies the condition.

Time and Space Complexity Analysis

• Time Complexity: O(log n), where n is the length of the citations array. This is because we use binary search, which reduces the search space by half in each iteration.

• Space Complexity: O(1). The algorithm uses only a few constant extra variables.

Code Implementation in Multiple Languages

The following code demonstrates the solution using several popular programming languages. The core logic remains the same across all implementations.

Python3:

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

Java:

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

C++:

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

Go:

func hIndex(citations []int) int {
	n := len(citations)
	left, right := 0, n
	for left < right {
		mid := (left + right + 1) / 2 //Integer division
		if citations[n-mid] >= mid {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

(Other languages like TypeScript, Rust, and C# would follow a similar pattern, with minor syntax adjustments.)

This detailed explanation provides a comprehensive understanding of the problem, the algorithm, and its implementation in various programming languages, along with a clear complexity analysis.