H Index Ii - Leetcode Solution

Problem Description: Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist 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."

Examples:

1. Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

2. Input: citations = [1,2,100] Output: 2 Explanation: [1,2,100] means the researcher has 3 papers in total and each of them had received 1, 2, 100 citations respectively. The researcher has 2 papers with at least 2 citations each and the remaining one with no more than 2 citations, so their h-index is 2.

Approach: The given citations list is sorted in ascending order. Therefore, we can use a binary search technique to find the h-index.

We can use two pointers to maintain the number of papers with at least h citations and the number of papers with no more than h citations. Initially, both pointers will start from opposite ends of the citations list.

Next, we calculate the mid-point between the pointers and check whether the mid-point is a valid h-index. A mid-point is a valid h-index if it satisfies the h-index condition described above.

If the mid-point is a valid h-index, then we update the minimum h-index found so far. We also move the pointer for papers with at least h citations towards the left to search for a lower h-index.

On the other hand, if the mid-point is not a valid h-index, then we move the pointer for papers with no more than h citations towards the right to search for a higher h-index.

We repeat these steps until the two pointers meet.

Solution:

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

Explanation: We used binary search to find the h-index value. We set the left pointer to 0 and right pointer to n-1 of the citations list. We used a while loop to iterate until the left pointer is less than or equal to the right pointer.

In each iteration, we defined the midpoint index, mid=(left+right)//2, to check if this point can satisfy the "At least h citations" criteria. If this condition is True, we update the current h_index value and move the pointer towards the left to check if we can find a smaller h_index value. Otherwise, we move the pointer towards the right to check if we can find a larger h_index value. This way, we search for the h_index value using a binary search approach.

Finally, we return the h_index value.

Time Complexity: The binary search runs in O(log n), where n is the number of papers. Therefore, the overall time complexity of this algorithm is O(log n).

Space Complexity: This algorithm requires a constant amount of additional space. Therefore, the space complexity of this algorithm is O(1).

1