How I solved the infamous H-index problem in Linear Time

The H-index score of a researcher is the largest integer H such that the researcher has H papers with at least H citations each.

In this problem, we are given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, to return the researcher's h-index. Also note that the H-Index is always less than or equal to the size of the given array (citations.length), where array size is always greater than zero.

Most programmers tend to try solving this problem by first sorting the array which would lead to a time complexity of O(N*logN). In this article, the aim is to get the job done in O(N). For example given an array of integers {1, 3, 3, 2, 2, 15}, the H-Index of the given array is 3 because there are at least 3 papers with at least 3 citations i.e.(3,3,15). Let's consider another array {2,0,6,1,5}, the H-Index of this array is 2 and not 3 because there are at least 2 (>=2) papers with at least 2 citations (2,6,5).

The idea is to start with the smallest possible value of H-Index(0) and then get the highest possible value of H-Index after iterating the loop(Time Complexity of O(N)). A HashMap is used to store the numbers of papers with the same number of citations where the no of citations is greater that the ith value of H-Index. In the solution below currentHIndex is the H-Index of the first i terms and tempIndex is the number of papers with at least currentHIndex plus 1(one) citations.

public class HIndex 
    public static void main(String[] args){
        System.out.println(
            hIndex(new int[] { 1, 3, 3, 2, 2, 15 }));
    }


    public static int hIndex(int[] citations)
    {
        /* A HashMAp to get the numbers of papers with the same number of citations only when citation[i] > currentHIndex */
        Map<Integer, Integer> map = new HashMap<>();
        int currentHIndex = 0; // the hIndex of the first i terms.
        int tempIndex = 0; // the number of papers with citations of at least "currentHIndex + 1"
        for (int i = 0; i < citations.length; i++) {


            /* adding only elements that are greater than the currentHIndex to the HashMap and their frequencies as keyValue*/
            if (citations[i] > currentHIndex) {
                if (map.containsKey(citations[i]))
                    map.put(citations[i],
                            1 + map.get(citations[i]));
                else
                    map.put(citations[i], 1);
                /* increase the value of tempIndex by 1 since citations[i] is greater than currentHIndex*/
                tempIndex += 1;
            }
            if (map.containsKey(currentHIndex)) {
                tempIndex -= map.get(currentHIndex); //remove the number of papers of a citatoins of the value of currentHIndex
                map.remove(currentHIndex);//ensuring that the map only contains key-value pair with key > currentHIndex
            }


            /* if there are at least "currentHIndex + 1" papers with at least "currentHIndex + 1" citations update currentHindex to the value of tempIndex */
            if (tempIndex > currentHIndex)currentHIndex = tempIndex;
        }
        return currentHIndex;
    }
}

{