# Java O(n log n) time, O(1) space with Explanation

• Idea is we need to find if there exist a position in sorted array, that citation[i] >= citation.length - i.

for example:

``````2 5 6 9 10 12 15
7 6 5 4 3  2  1   <=== reverse index, tells how many elements(inclusive) to the right.
``````

in order to find the h-index. we need to find if there exist a position that citation[i] >= reverse index.

``````So, like
check elements 2 and after >= 7? --> No
check elements 5 and after >= 6? --> No
check elements 6 and after >= 5? --> Yes! This is the max "h" value, we return this 5.
``````

Code:

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

Arrays.sort(citations);
for(int i = 0; i < citations.length; i++){
if(citations[i] >= citations.length - i)
return citations.length - i;
}
return 0;
}
}
``````

Time Complexity O(n log n) + O(n) = O(n log n)
Space Complexity O(1)

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

• Thanks for the followed comment. in your "h = 3" statement, I think that's right. there are 3 papers which is [7 8 9] have at least 3 citations and the other 2 paper which is [1 3] DO NOT have MORE THAN 3 citations each. May I know what is your reason claiming that this statement is obviously wrong?

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