algoadvance

Leetcode 274. H

Problem Statement

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

The H-Index is defined as follows: A scientist has an index h if h of their n papers have at least h citations each, and the other n - h papers have no more than h citations each.

Clarifying Questions

  1. Input Constraints:
    • What is the range of the size of the citations array?
    • Can the elements of the citations array be negative?
  2. Output:
    • Should the output be an integer representing the H-Index?
  3. Edge Cases:
    • How should the function handle the case where there are no papers?

Strategy

To determine the H-Index, let’s follow these steps:

  1. Sort the citations array in non-decreasing order.
  2. Iterate from the end of the sorted array and find the maximum value of h where citations[i] >= h.

Code

Below is the implementation in C++:

#include <vector>
#include <algorithm>

int hIndex(std::vector<int>& citations) {
    std::sort(citations.begin(), citations.end(), std::greater<int>());
    int h = 0;
    for (int i = 0; i < citations.size(); i++) {
        if (citations[i] >= i + 1) {
            h = i + 1;
        } else {
            break;
        }
    }
    return h;
}

Explanation

  1. Sorting:
    • We start by sorting the array in descending order.
    • This allows us to count from the highest citation downward and find the largest h where there are at least h papers with h or more citations.
  2. Iteration:
    • We iterate over the sorted array and check if the current paper’s citation count is greater than or equal to the current index + 1 (to handle 0-based indexing).
    • We update h to be the maximum value of i + 1 where the condition holds.

Time Complexity

  1. Sorting: O(n log n), where n is the number of papers.
  2. Iteration: O(n), iterating through the sorted array.

Thus, the overall time complexity is O(n log n). This efficiency is suitable for typical input sizes in coding interviews and real-world scenarios.

I hope this helps! Feel free to ask if you have any questions or need further clarifications.

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