## Saturday, December 7, 2019

### Problem Statement

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
Example:
```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, her h-index is `3`.```
Note: If there are several possible values for h, the maximum one is taken as the h-index.
Hint 1
An easy approach is to sort the array first.
Hint 2
What are the possible values of h-index?

Hint 3
A faster approach is to use extra space.

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

It’s not the most straightforward question to understand I have to admit that. I normally start with small examples to help me understand

The requirement is: his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each

What happens if citation contains only 1 element?
• Citations =  , N = 1, h = 1, N-h = 0
This gives us hint that h has an upper bound of N

What happens if citation contains only 2 elements? And we can assign some large citation values
• Citations = [1000, 2000] , N = 2, h = 2. It seems h-index has not too much to do with the citation values itself, rather it’s about the index and the values.

We should now have a super brute force way, since h is bounded to be [0, N], we just go through each value and try to see if it could meet the h criteria (e.g., we start from N, then we see if there is at least N papers that have at least N citations) This would result in a O(N^2) time complexity.

Naturally, we normally can think of if we can sort the array to reduce the time complexity. After sort, using the below graph, the problem becomes find the citation more than the citation array index, and that citation index could be the h-index (that's why it's called h-index, not h-value, it's about index). This would give a O(NlgN) time complexity. Code is attached in the References section. source: leetcode solution

Finally, we can think about bucket sort since h-index is bounded from [0, N], and if paper citations are larger than N, it's just considered on counting on index N.

You know how to do a bucket sort 😄

### Solutions

#### Use bucket sort

Time Complexity: O(N) since we went through citations only once
Space Complexity: O(N) since we are using an extra array to keep track of the count