Introduction
LeetCode 274: H-Index is a problem inspired by a real-world academic metric. It challenges you to compute a researcher’s H-Index given an array of citations per paper.
This is a common question in interviews where you're expected to apply sorting, greedy strategies, or even counting approaches efficiently.
What is the H-Index?
The H-Index is defined as:
A researcher has an H-Index of h if they have at least h papers with at least h citations each, and the rest have no more than h citations.
Problem Statement
Given an array of integers citations (where citations[i] is the number of citations for a researcher's i-th paper), return their H-Index.
Examples
python
Input: citations = [3, 0, 6, 1, 5]
Output: 3
Explanation:
- 3 papers have at least 3 citations → H-Index is 3
python
Input: citations = [1, 3, 1]
Output: 1
✅ Step-by-Step Solution in Python
🧠 Strategy 1: Sort and Count
We sort the citations in descending order and look for the maximum value where citations[i] >= i + 1.
🔁 Step-by-Step
Input: [3, 0, 6, 1, 5]
Sorted: [6, 5, 3, 1, 0]
- i = 0 → 6 ≥ 1 ✅
- i = 1 → 5 ≥ 2 ✅
- i = 2 → 3 ≥ 3 ✅
- i = 3 → 1 ≥ 4 ❌
So H-Index = 3
✅ Python Code
python
class Solution:
def hIndex(self, citations: list[int]) -> int:
citations.sort(reverse=True)
for i, c in enumerate(citations):
if c < i + 1:
return i
return len(citations)
⏱️ Time and Space Complexity
OperationTime ComplexitySpace ComplexitySortO(n log n)O(1) or O(n)CountO(n)O(1)
🧠 Bonus Strategy: Bucket Sort (O(n) Time)
This works when citations[i] are bounded by the length of the array (n).
✅ Python Code (Bucket Sort)
python
class Solution:
def hIndex(self, citations: list[int]) -> int:
n = len(citations)
buckets = [0] * (n + 1)
for c in citations:
if c >= n:
buckets[n] += 1
else:
buckets[c] += 1
total = 0
for i in range(n, -1, -1):
total += buckets[i]
if total >= i:
return i
return 0
💡 Example Dry Run: [3, 0, 6, 1, 5]
Buckets =
[1, 1, 0, 1, 0, 2]
From i=5 down to 0, once total count ≥ i, return i → Output = 3
🔍 Edge Cases
- Empty list →
0
- All zeros →
0
- All large values → min(n, min(citations))
✅ Conclusion
LeetCode 274: H-Index is a clever mix of:
- Sorting logic
- Greedy checks
- Optional bucket sort for optimal time