Problem of The Day: H-Index

Problem Statement

Intuition

The intuition behind the solution is to sort the citations in ascending order and then iterate through the sorted list to find the H-index.

Approach

I will sort the citations in ascending order to make it easier to identify the h-index. Then, I will iterate through the sorted list in reverse order, starting from the highest number of citations. For each iteration, I’ll check if the current number of citations is greater than the number of papers already considered. If it is, I’ll increment the count of papers. I’ll continue this process until I find the maximum h-index.

Complexity

• Time complexity: O(nlogn) due to sorting

• Space complexity: O(1)

Code

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        res = 0
        citations.sort()
        N = len(citations)
        papers = 0
        for i in reversed(range(N)):
            if citations[i] > papers:
                papers += 1
            if papers <= citations[i]:
                res = max(res, papers)
        return res

Editorial solution

Approach #1 (Sorting) [Accepted]

Implementation in Java

public class Solution {
    public int hIndex(int[] citations) {
        // sorting the citations in ascending order
        Arrays.sort(citations);
        // finding h-index by linear search
        int i = 0;
        while (i < citations.length && citations[citations.length - 1 - i] > i) {
            i++;
        }
        return i; // after the while loop, i = i' + 1
    }
}

Implementation in Python

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse=True)
        h = 0

        while h < len(citations) and citations[h] > h:
            h += 1

        return h

Approach #2 (Counting) [Accepted]

public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] papers = new int[n + 1];
        // counting papers for each citation number
        for (int c: citations)
            papers[Math.min(n, c)]++;
        // finding the h-index
        int k = n;
        for (int s = papers[n]; k > s; s += papers[k])
            k--;
        return k;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)