H-Index (Sorting Approach)

Problem Statement

Given citations (citations per paper), compute the h-index: the largest h such that at least h papers have >= h citations each.

Example

Input:  citations = [3, 0, 6, 1, 5]
Output: 3

Approach

Sort citations in descending order. Walk the list: while the paper at position i (0-based) has at least i + 1 citations, the h-index can be i + 1. Stop as soon as the condition fails.

Complexity

• Time: O(n log n)
• Space: O(1) extra (ignoring the sort)

Solution Code

Python

def hIndex(citations):
    citations.sort(reverse=True)
    h = 0
    for i, c in enumerate(citations):
        if c >= i + 1:
            h = i + 1
        else:
            break
    return h

Java

int hIndex(int[] citations) {
    Integer[] c = Arrays.stream(citations).boxed().toArray(Integer[]::new);
    Arrays.sort(c, Collections.reverseOrder());
    int h = 0;
    for (int i = 0; i < c.length; i++) {
        if (c[i] >= i + 1) h = i + 1;
        else break;
    }
    return h;
}

C++

int hIndex(vector<int>& citations) {
    sort(citations.rbegin(), citations.rend());
    int h = 0;
    for (int i = 0; i < (int)citations.size(); i++) {
        if (citations[i] >= i + 1) h = i + 1;
        else break;
    }
    return h;
}

Key Takeaways

• Sorting descending lets a single scan find the crossover point.
• A counting-sort variant solves it in O(n); the pre-sorted version is H-Index II.
• Reference: LeetCode 274 (H-Index).