# O(n) Java solution using O(n) space

• Explanation: The idea is to use another array, index is the citation and value is the number of papers that has at least the citation. Since the h-index can only be n, the new array will only need the index to be at most n, thus the array size will only need n+1. Papers that have more than n citations will store in array[n].
Go through the array based on h index definition: array[i]>=i, find the max value of i.

``````public class Solution {
public int hIndex(int[] citations) {
if(citations == null || citations.length == 0) return 0;

int n = citations.length;
int[] num = new int[n+1];

for(int i=0; i<n; i++) {
if(citations[i]>n) num[n]++;
else num[citations[i]]++;
}

if(num[n]>=n) return n;
for(int i=n-1; i>=0; i--) {
num[i] += num[i+1];
if(num[i]>=i) return i;
}
return 0;
}
}``````

• Hi,

I came across a situation: given citations = [3, 1, 7, 8, 9]. What will be the answer be?

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."

When h=3, the definition will be "A scientist has index 3 if 3 of his/her 5 papers have at least 3 citations each, and the other 2 papers have no more than 3 citations each." Obviously wrong....

When h=4, the definition will be "A scientist has index 4 if 4 of his/her 5 papers have at least 4 citations each, and the other 1 papers have no more than 4 citations each." Obviously wrong....

When h=2, the definition will be "A scientist has index 2 if 2 of his/her 5 papers have at least 2 citations each, and the other 3 papers have no more than 3 citations each." Obviously wrong....

• h index would be 3 in this case. As 7,8,9>=3 and 1,3 <=3 (The definition of h index "...no more than")

• yeah, exact same idea as mine :)

• There is one way you can simplify it by removing if(num[n]>=n) return n;
In that case, instead of overriting in num array, you can maintain an integer sum = 0 and start from length index.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.