# 274. H-Index

## Approach 1: Bucket

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int hIndex(vector& citations) { const int n = citations.size(); int accumulate = 0; vector count(n + 1); for (const int citation : citations) ++count[min(citation, n)]; // To find the largeset h-index, loop from back to front // I is the candidate h-index for (int i = n; i >= 0; --i) { accumulate += count[i]; if (accumulate >= i) return i; } throw; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int hIndex(int[] citations) { final int n = citations.length; int accumulate = 0; int[] count = new int[n + 1]; for (final int citation : citations) ++count[Math.min(citation, n)]; // To find the largeset h-index, loop from back to front // I is the candidate h-index for (int i = n; i >= 0; --i) { accumulate += count[i]; if (accumulate >= i) return i; } throw new IllegalArgumentException(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def hIndex(self, citations: List[int]) -> int: n = len(citations) accumulate = 0 count = [0] * (n + 1) for citation in citations: count[min(citation, n)] += 1 # To find the largeset h-index, loop from back to front # I is the candidate h-index for i, c in reversed(list(enumerate(count))): accumulate += c if accumulate >= i: return i 

## Approach 2: Sort

• Time: $O(n\log n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int hIndex(vector& citations) { const int n = citations.size(); sort(begin(citations), end(citations)); for (int i = 0; i < n; ++i) if (citations[i] >= n - i) return n - i; return 0; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int hIndex(int[] citations) { final int n = citations.length; Arrays.sort(citations); for (int i = 0; i < n; ++i) if (citations[i] >= n - i) return n - i; return 0; } } 
  1 2 3 4 5 6 7 8 9 10 11 class Solution: def hIndex(self, citations: List[int]) -> int: n = len(citations) citations.sort() for i, citation in enumerate(citations): if citation >= n - i: return n - i return 0