274.H-Index(Medium).md

274. H-Index (Medium)

Date and Time: Sep 7, 2024, 13:13 (EST)

Link: https://leetcode.com/problems/h-index/

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

Constraints:

• n == citations.length

• 1 <= n <= 5000

• 0 <= citations[i] <= 1000

Walk-through:

1. Sorting

We sort citations in descending order. Then we enumerate(citations) to get the index and citations for each index. We know when index >= c is the maximum h we can get (it means at least i papers have i citations.). Otherwise, we just return len(citations), because h cannot exceed the number of papers we have, so the maximum we can have is len(citations), which means we have len(citations) papers.

Example 1:
# citations = [6, 5, 3, 1, 0]
# index =     [0, 1, 2, 3, 4]

Example 2:
# [5, 4, 4, 4]
# [0, 1, 2, 3]

2. counts

In this approach, we create a list counts[] with range [0, len(citations) + 1] (because h-index will not exceed the number of papers (len(citations))) and update each index with the number of papers that have "index" citation number, so index 0 means how many papers have 0 citations, and the last index means how many paper have at least the last index's citation.

After we loop over citations, we can start from backward, and we have two variables h = len(citations) and papers which is current number of papers we have. We return until we have papers >= h.

Example:
citations = [5, 1, 2, 8, 9, 3], counts = [0, 1, 1, 1, 0, 1, 2] 
                                          0, 1, 2, 3, 4, 5, 6
                                h = 3, papers = 4

Python Solution:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        # Sort citations in descending order, find when index >= citation

        # TC: O(nlogn), n = len(citations), SC: O(1)
        citations.sort(reverse=True)
        for i, citation in enumerate(citations):
            if i >= citation:
                return i
        return len(citations)

Time Complexity: $O(nlog\ n)$
Space Complexity: $O(1)$

Python Optimized Solution:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        counts = [0] * (n + 1)
        for c in citations:
            counts[min(c, n)] += 1

        h, papers = n, counts[n]
        while papers < h:
            h -= 1
            papers += counts[h]
        return h

Time Complexity: $O(n)$
Space Complexity: $O(n)$