275. H-Index II

Description

The h-index is a metric that measures both the productivity and citation impact of a researcher's publications. The h-index is defined as the maximum value of h such that the given author has published at least h papers that have each been cited at least h times.

Given an array citations where citations[i] is the number of citations a researcher received for their i-th paper, calculate the researcher's h-index.

Intuition

The h-index represents the highest number of papers h that have at least h citations. The problem can be visualized by counting how many papers have each possible citation count. If we aggregate these counts, starting from the highest possible citation count, we can determine the largest h where at least h papers have h or more citations.

Approach

1. Count Citations: - First, determine the maximum citation in the array. - Create an array counts of size maxCitation + 1 to store how many papers have each specific citation count.
2. Aggregate Paper Counts: - Iterate through the citation array and update the counts array with the number of papers for each citation count.
3. Determine h-Index: - Start from the highest possible citation count and accumulate the number of papers. - Check if the accumulated number of papers is greater than or equal to the current citation count h. If so, that h is the h-index.
4. Edge Case: - If no such h is found, return 0, though by definition, the h-index should be at least 0.

Complexity

Time Complexity:

• The time complexity is O(n), where n is the length of the citation array. We make a single pass to count the citations and another pass to determine the h-index.

Space Complexity:

• The space complexity is O(m), where m is the maximum citation count in the array. This space is used for the counts array to store the number of papers with each possible citation count.

Code

C++

class Solution {
public:
    int hIndex(std::vector& citations) {
        int maxCitation = *std::max_element(citations.begin(), citations.end());
        std::vector counts(maxCitation + 1, 0);
        
        // Step 1: Count the number of papers for each citation count
        for (int citation : citations) {
            counts[citation]++;
        }
        
        int totalPapers = 0;
        
        // Step 2: Calculate how many papers have at least `h` citations
        for (int h = maxCitation; h >= 0; h--) {
            totalPapers += counts[h];
            if (totalPapers >= h) {
                return h;
            }
        }
        
        return 0; // Fallback
    }
};

Python

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        max_citation = max(citations)
        counts = [0] * (max_citation + 1)
        
        # Step 1: Count the number of papers for each citation count
        for citation in citations:
            counts[citation] += 1
        
        total_papers = 0
        
        # Step 2: Calculate how many papers have at least `h` citations
        for h in range(max_citation, -1, -1):
            total_papers += counts[h]
            if total_papers >= h:
                return h
        
        return 0  # Fallback

Java

class Solution {
    public int hIndex(int[] citations) {
        int maxCitation = Arrays.stream(citations).max().getAsInt();
        int[] counts = new int[maxCitation + 1];
        
        // Step 1: Count the number of papers for each citation count
        for (int citation : citations) {
            counts[citation]++;
        }
        
        int totalPapers = 0;
        
        // Step 2: Calculate how many papers have at least `h` citations
        for (int h = maxCitation; h >= 0; h--) {
            totalPapers += counts[h];
            if (totalPapers >= h) {
                return h;
            }
        }
        
        return 0; // Fallback
    }
}

JavaScript

function hIndex(citations) {
    const maxCitation = Math.max(...citations);
    const counts = new Array(maxCitation + 1).fill(0);
    // Step 1: Count the number of papers for each citation count
    for (let citation of citations) {
        counts[citation]++;
    }
    let totalPapers = 0;

    // Step 2: Calculate how many papers have at least `h` citations
    for (let h = maxCitation; h >= 0; h--) {
        totalPapers += counts[h];
        if (totalPapers >= h) {
            return h;
        }
    }
    return 0; // Fallback, though h-index should be at least 0
}