H-Index Leetcode Solution

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 i^th 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 $5$. The counts are [1,1,0,1,0,2$]$. The first k from right to left (5 down to $0$) 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.