13. [Counting Sort]: H-index

Counting sort

274. H-Index

Medium

227

60

Companies

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

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1

Constraints:

• n == citations.length

• 1 <= n <= 5000

• 0 <= citations[i] <= 1000

H-Index - LeetCode

Counting Sort

time: O(maxNum), the max cited num

Space: O(n), n is the max cited num

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    const counts = [];

    for (let i = 0; i < citations.length; i++) {
        const curr = citations[i];
        counts[curr] = counts[curr] ?? 0;
        counts[curr] += 1;
    }

    const sum = [];
    sum[counts.length - 1] = counts[counts.length - 1] ?? 0;
    for (let i = counts.length - 1; i >= 1; i--) {
        const prev = counts[i - 1] ?? 0;
        // console.log(sum[i], prev);
        sum[i - 1] = sum[i] + prev;
    }

    for (let i = counts.length; i >= 0; i--) {
        const currSum = sum[i];
        if (currSum >= i) return i;
    }

    return 0;
};

Bucket Sort

Java bucket sort O(n) solution with detail explanation - H-Index - LeetCode

time: O(N), N is the number of paper

space: O(1)

public int hIndex(int[] citations) {
    int n = citations.length;
    int[] buckets = new int[n+1];
    for(int c : citations) {
        if(c >= n) {
            buckets[n]++; // genius
        } else {
            buckets[c]++;
        }
    }
    int count = 0;
    for(int i = n; i >= 0; i--) {
        count += buckets[i];
        if(count >= i) {
            return i;
        }
    }
    return 0;
}