## 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).

- So we create an array “papers_freq” which acts like a HashMap and loops backward from the highest element.
- Then we find “totalCitations ” which is the total number of papers that has more than i citations.
- We terminate when a total number of papers with more than i citations >= i (totalCitations >=i ).
- 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.