We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

H-Index II

Difficulty: Medium

Problem Description

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i-th paper and citations is sorted in ascending order, return the researcher's h-index. The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Key Insights

  • The h-index can be determined by checking how many papers have at least a certain number of citations.
  • Since the citations array is sorted in ascending order, a binary search approach is suitable for efficiently finding the h-index.
  • The h-index is defined such that if a researcher has h papers with at least h citations, then the h-index is h.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

We can use binary search to find the h-index in the sorted citations array. The idea is to maintain two pointers, left and right, to represent the search range. For each midpoint mid, we check if the number of papers from that point onward (which is n - mid) is at least citations[mid]. If it is, we update our potential h-index and search in the right half; otherwise, we search in the left half. This allows us to efficiently narrow down the potential h-index value.

Code Solutions

def hIndex(citations):
    n = len(citations)
    left, right = 0, n - 1

    while left <= right:
        mid = left + (right - left) // 2
        if citations[mid] < n - mid:
            left = mid + 1  # Move right
        else:
            right = mid - 1  # Move left

    return n - left  # The h-index is the number of papers left
← Back to All Questions