Find H-Index

Given an integer array citations[], where citations[i] is the number of citations a researcher received for the i^th paper. The task is to find the H-index.

H-Index is the largest value such that the researcher has at least H papers that have been cited at least H times.

Examples:

Input: citations[] = [3, 0, 5, 3, 0]
Output: 3
Explanation: There are at least 3 papers (3, 5, 3) with at least 3 citations.

Input: citations[] = [5, 1, 2, 4, 1]
Output: 2
Explanation: There are 3 papers (with citation counts of 5, 2, and 4) that have 2 or more citations. However, the H-Index cannot be 3 because there aren't 3 papers with 3 or more citations.

Input: citations[] = [0, 0]
Output: 0

Constraints:
1 ≤ citations.size() ≤ 10⁶
0 ≤ citations[i] ≤ 10⁶

Approach 01:

// User function Template for C++

class Solution {
  public:
    // Function to find hIndex
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int maxHIndex = 0;
        int totalPapers = citations.size();
        
        for (int reverseIndex = totalPapers - 1; reverseIndex >= 0; reverseIndex--) {
            int currentHIndex = min(citations[reverseIndex], totalPapers - reverseIndex);
            maxHIndex = max(maxHIndex, currentHIndex);
        }
        
        return maxHIndex;
    }
};

class Solution:
    def hIndex(self, citations):
        citations.sort()
        maxHIndex = 0
        totalPapers = len(citations)
        
        for reverseIndex in range(totalPapers - 1, -1, -1):
            currentHIndex = min(citations[reverseIndex], totalPapers - reverseIndex)
            maxHIndex = max(maxHIndex, currentHIndex)
        
        return maxHIndex

Time Complexity

• Sorting the citations:

  The function begins by sorting the citations array. Sorting takes \(O(N \log N)\), where \(N\) is the number of elements in the array.

• Iterating over the sorted array:

  The subsequent loop iterates over the sorted array in reverse order, which takes \(O(N)\).

• Overall Time Complexity:

  The dominant operation is the sorting step, so the overall time complexity is \(O(N \log N)\).

Space Complexity

• Sorting operation:

  The sorting operation may use \(O(N)\) additional space depending on the sorting algorithm implementation (e.g., for quicksort or mergesort). For in-place sorting like heapsort, this would be \(O(1)\).

• Auxiliary variables:

  The function uses a few integer variables (maxHIndex, totalPapers, reverseIndex, and currentHIndex), which require \(O(1)\) space.

• Input array:

  The input array citations is passed by reference, so no additional space is required for it.

• Overall Space Complexity:

  The overall space complexity is \(O(N)\) if the sorting algorithm uses additional space; otherwise, it is \(O(1)\) for in-place sorting.