[LeetCode] 274. H-Index

1. Question

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 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.

Example 2:

Input: citations = [1,3,1]
Output: 1

2. Thoughts

1. Iterate through the index, and save citation number per citation in a dictionary
2. make the sum so that lower ++ its ancestors
3. While iterating Dictionary, return least h paper that has cited at least h time.

3. Tips learned

3.1. Iterate Dictionary

Can I iterating the dictionay backwards?

citation_nums_list = list(citation_nums)
citation_nums_list.sort(reverse=True)  # 역순으로 정렬

for citation_num in citation_nums_list:
    print(citation_num, ":", citation_mapping[citation_num])
    
# Backwards
for citation_num in reversed(list(citation_mapping.keys())):
    print(citation_num, ":", citation_mapping[citation_num])

4. My solution

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citation_mapping = {}

        for citation in citations:
            if citation not in citation_mapping:
                citation_mapping[citation] = 1
            else:
                citation_mapping[citation] += 1

        min_count = 0
        for citation in reversed(sorted(citation_mapping.keys())):
            min_count += citation_mapping[citation]
            if min_count >= citation:
                return max(min_count - citation_mapping[citation], citation)

        return len(citations)

81/81 cases passed (43 ms)
Your runtime beats 66.95 % of python3 submissions
Your memory usage beats 24.62 % of python3 submissions (17.6 MB)

5. AI Solution and Improvements

The provided algorithm for computing the h-index has a good approach, but it can be optimized for better efficiency. The algorithm uses a hash map to count the frequency of each citation number and then iterates over these counts in descending order to find the maximum h-index. However, this approach can be improved both in terms of simplicity and efficiency.

Here's an optimized approach:

1. Sort the Citations Array: Sort the citations array in descending order. This way, higher citations come first, and it's easier to find the h-index.

2. Iterate Through the Sorted Array: Iterate through the sorted array, and at each step, check if the citation count at the current index is greater than or equal to the index (considering 1-based indexing). The maximum such index is the h-index.

3. Edge Cases: Handle cases where the array is empty or all citations are zero.

This method avoids the use of a hash map and reduces the complexity. Here's how the revised code looks:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        # Sort the citations in descending order
        citations.sort(reverse=True)
        
        # Iterate through the citations to find the h-index
        for i, citation in enumerate(citations):
            if citation <= i:
                return i

        # If all papers have more citations than their rank
        return len(citations)

This code is more efficient because:

• It only sorts and iterates through the array once.
• It does not use extra space for a hash map.
• It stops as soon as it finds the h-index, which can be faster in cases where the h-index is found early in the sorted array.