algoadvance

Leetcode 275. H

Problem Statement:

Imagine you have a sorted array of integers citations where citations[i] represents the number of citations a researcher has received for their i-th paper. Your task is to compute the researcher’s h-index.

The h-index is defined as follows:

• A scholar 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.

Given that the citations array is sorted in ascending order, design an algorithm to compute the h-index.

You must write an efficient algorithm with a time complexity less than or equal to O(log N).

Clarifying Questions:

1. Input Size: What is the maximum size for the citations array?
   • Typically, LeetCode problems handle arrays up to 10^5 elements.
2. Type of Elements: Are the elements in the citations array guaranteed to be integers?
   • The problem statement implies they will be.
3. Edge Cases: How should the function handle cases where the citations array is empty?
   • If the array is empty, the h-index should be 0.

With these clarifications, we’re ready to devise a solution.

Strategy:

Given the array is sorted, we can leverage binary search to find the h-index efficiently. The idea is to factor in the position of each paper in the array relative to its citation count, given the definition of the h-index.

1. Binary Search Approach:
   • Use two pointers (left and right) to represent the start and end of the array.
   • For each middle element, compute if it can be the h-index.
   • Adjust the search based on whether the computed values meet the h-index criteria.

Code:

Here is the C++ implementation:

#include <vector>
using namespace std;

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // Number of papers with at least citations[mid] citations is (n - mid)
            if (citations[mid] == n - mid) {
                return citations[mid];
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return n - left;
    }
};

Explanation:

1. Initialize left to 0 and right to the last index of the array.
2. Perform binary search until left exceeds right:
   • Calculate the mid-point of the array.
   • Determine if the citation count at mid index satisfies the condition of the h-index (i.e., there are at least n - mid papers with citations[mid] or more citations).
   • If true, return citations[mid].
   • If citations[mid] is less than n - mid, it means there are not enough papers with at least mid citations, move the left pointer to mid + 1.
   • Otherwise, move the right pointer to mid - 1.
3. If no exact match is found, return n - left, which will be the h-index.

Time Complexity:

• The algorithm runs in O(log N) time because it uses binary search.
• Space complexity is O(1) since we are using a constant amount of extra space.

This efficient approach ensures that the h-index is computed quickly even for large arrays.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?