# H-Index Leetcode Solution

Difficulty Level Medium
ArrayViews 5710

## Problem Statement:

H-Index Leetcode solution says that – Given an array of integers “citations” where citations[i] is the number of citations a researcher received for their ith paper, return researcher’s H-Index. If several H-Index values are present, return the maximum among them.

Definition of H-Index:  A scientist has an index “h” if h of their 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:

citations = [3, 0, 6, 1, 5] means there are  5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. As the researcher has 3 papers with at least 3 citations (3, 6, 5) and the other remaining two with no more than 3 citations (0, 1). So the H-Index will be 3 in this case.

After replacing 6 with n = 5, we have citations = [3,0,5,1,5]. Now, we count the number of papers for each citation number 0 to . The counts are [1,1,0,1,0,2. The first k from right to left (5 down to ) that have k<=s is the h-index 3.

cutting off the area with citations more than n

### Example 2:

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

## Approach:

### Idea:

To solve this problem we use the Counting Sort technique with a little trick.

The idea is to see that the result can only range from 0 to the length of the array (because we can’t have an h-index greater than the total papers published).

1. So we create an array “papers_freq” which acts like a HashMap and loops backward from the highest element.
2.  Then we find “totalCitations ” which is the total number of papers that has more than i citations.
3. We terminate when a total number of papers with more than i citations >= i  (totalCitations >=i ).
4. We don’t need to keep going because we are trying the biggest i possible, we stop and return the result.

## Code:

### C++ code for H-Index Leetcode Solution :

class Solution {
public:
int hIndex(vector<int>& citations) {
int len = citations.size();

vector<int> papers_freq(len+1);
for(int c: citations) {
if(c > len) {
papers_freq[len]++;
} else {
papers_freq[c]++;
}
}

int totalCitations = 0;
for(int i = len; i >= 0; i--) {
totalCitations += papers_freq[i];
if(totalCitations >= i) {
return i;
}
}

return -1;
}
};

### Java code for H-Index Leetcode Solution :

class Solution {
public int hIndex(int[] citations) {

int len = citations.length;

int[] papers_freq = new int[len+1];
for(int c: citations) {
if(c > len) {
papers_freq[len]++;
} else {
papers_freq[c]++;
}
}

int totalCitations = 0;
for(int i = len; i >= 0; i--) {
totalCitations += papers_freq[i];
if(totalCitations >= i) {
return i;
}
}

return -1;
}
}

## Complexity Analysis for H-Index Leetcoee Solution:

### Time Complexity:

The Time Complexity will be O(N), first, we need to traverse the “citations” array once which needs O(N) time. Then for finding the H-Index we need another O(N) since we traverse the papers_freq array at most once. So, we can say that the overall time complexity of the code will be O(N).

### Space Complexity:

Space Complexity will be O(N) since we use extra space to store the counts.

Translate »