# 13. \[Counting Sort]: H-index

[#counting-sort](https://algorithm.prettylog.com/overview/readme/counting-sort/counting-sort#counting-sort "mention")

**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](https://en.wikipedia.org/wiki/H-index): 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](https://leetcode.com/problems/h-index/)

### Counting Sort

> time: O(maxNum), the max cited num

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

```jsx
/**
 * @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](https://leetcode.com/problems/h-index/solutions/70768/java-bucket-sort-o-n-solution-with-detail-explanation/)

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

> space: O(1)

```jsx
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;
}
```