algoadvance

Leetcode 274. H

Problem Statement

The H-Index is a metric that measures both the productivity and citation impact of the publications of a scholar. Given an array of integers citations where citations[i] is the number of citations a researcher received for their i-th paper, write a function to compute the researcher’s H-Index.

The definition of the H-Index is as follows:

Example 1:

Input: citations = [3, 0, 6, 1, 5]
Output: 3
Explanation: [3, 0, 6, 1, 5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. 
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their H-index is 3.

Example 2:

Input: citations = [1, 3, 1]
Output: 1

Clarifying Questions

  1. Q: Can citations have negative values?
    • A: No, citations are always non-negative integers.
  2. Q: What if the citations array is empty?
    • A: An empty array would result in an H-index of 0.
  3. Q: Are the elements in citations always integers?
    • A: Yes, all citation counts are integers.

Strategy

To find the H-Index, follow these steps:

  1. Sorting: Sort the array of citations in descending order.
  2. Iterate and Compare: Iterate through the sorted array and compare each element with its index + 1 (because array indices are zero-based).
  3. Determine H-Index: The H-Index is the maximum value where the condition citations[i] ≥ i + 1 holds true.

Code

import java.util.Arrays;

public class Solution {
    public int hIndex(int[] citations) {
        // Step 1: Sort the array in descending order
        Arrays.sort(citations);
        int n = citations.length;
        int hIndex = 0;
        
        // Step 2: Iterate over the sorted array and determine the h-index
        for (int i = 0; i < n; i++) {
            int hCandidate = n - i;
            if (citations[i] >= hCandidate) {
                hIndex = hCandidate;
                break; // No need to continue since we found the max h-index
            }
        }
        
        return hIndex;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] citations1 = {3, 0, 6, 1, 5};
        System.out.println(solution.hIndex(citations1)); // Output: 3

        int[] citations2 = {1, 3, 1};
        System.out.println(solution.hIndex(citations2)); // Output: 1
    }
}

Time Complexity

  1. Sorting: The sorting step has a time complexity of (O(N \log N)), where (N) is the length of the citations array.
  2. Iteration: The iteration step is linear, (O(N)).

Since the sorting step dominates, the overall time complexity of the solution is (O(N \log N)).

This approach optimizes the calculation and ensures that we correctly find the H-Index efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI