H Index - Leetcode Solution

Problem Statement:

Given an array of citations (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."

Example:

Input: citations = [3,0,6,1,5] Output: 3

Explanation: The researcher has 5 publications with 3, 0, 6, 1, 5 citations respectively. The researcher's h-index is 3 because he/she has 3 papers with at least 3 citations.

Solution:

The h-index is a measure to quantify the productivity and citation impact of a researcher. The h-index is calculated based on the number of papers published and the number of citations that these papers receive. The index is based on the set of the researcher's most cited papers and the number of citations that they have received in other publications. Here is the detailed approach to solving the H-Index problem.

Step 1: Sort the citation values in ascending order. [0, 1, 3, 5, 6]

Step 2: For each citation value in the sorted list, calculate the number of papers that have a citation count equal to or greater than that. citations = [0, 1, 3, 5, 6] number of papers with citation ≥ 0: 5 number of papers with citation ≥ 1: 4 number of papers with citation ≥ 3: 3 number of papers with citation ≥ 5: 2 number of papers with citation ≥ 6: 1

Step 3: Determine the h-index as the maximum value of the minimum of each number of papers with citation ≥ i, where i is the citation count. For the above example, the h-index is 3, because the minimum of number of papers with citation ≥ 3 is 3.

The time complexity of the above algorithm is O(nlogn) because of the sorting. Here is the Python code that implements the above algorithm:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort()
        n = len(citations)
        for i in range(n):
            if citations[i] >= n - i:
                return n - i
        return 0

We can make the above algorithm more efficient by using bucket sort, where we create an array of size n+1 and keep track of the number of papers for each citation count. This reduces the time complexity to O(n) and makes the algorithm more scalable for large input sizes.

1