[LeetCode/Python] 274. H-Index

📌 Problem

[LeetCode] 274. H-Index

📌 Solution

1. Sorting Approach(1)

Code

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        citations = sorted(citations, reverse=True)

        h_idx = 0
        for i in range(n):
            if citations[i] >= i+1:
                h_idx += 1
        
        return h_idx

Complexity

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

2. Sorting Approach(2)

Idea

• Early exit: Return at the first c < i, avoiding unnecessary scans
• In-place sort: Uses list.sort() instead of sorted(), reducing extra $O(n)$ memory.
• Clear & robust: enumerate(..., start=1) + immediate return minimizes off-by-one risks

Code

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse=True)
        for i, c in enumerate(citations, start=1):
            if c < i:
                return i - 1
        return len(citations)

Complexity

• Time Complexity: $O(n log n)$
• Space Complexity: $O(1)$

3. Counting Sort Approach ⭐️

Idea

• Cap all citation counts at n (since h-index ≤ n)
• Build a frequency array of size n+1
• Traverse from n down to 0, keeping a running total of papers
• The first h where papers ≥ h is the h-index

Code

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

        papers = 0
        for h in range(n, -1, -1):
            papers += count[h]
            if papers >= h:
                return h

Complexity

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

For large-scale data or when optimal time complexity is required, the counting sort approach($O(n)$) is the best choice