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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

H-Index II

Number: 275

Difficulty: Medium

Paid? No

Companies: Amazon, Meta

Problem Description

Given a sorted array of citations in ascending order, determine the researcher's h-index. The h-index is the maximum value h such that the researcher has published at least h papers that have each been cited at least h times. You must design a logarithmic time solution.

Key Insights

  • The citations array is sorted in ascending order.
  • Use binary search to achieve a logarithmic time complexity.
  • The number of papers that have at least citations[i] citations is n - i, where n is the total number of papers.
  • Compare citations[mid] with n - mid to decide which part of the array to search next.

Space and Time Complexity

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

Solution

Perform a binary search on the sorted citations array. At any index mid, calculate the candidate h-index as n - mid. If citations[mid] is less than this candidate, it means not enough citations for the papers to the left, so search to the right. Otherwise, continue to search on the left to possibly find a higher h-index. The final answer is n - left after the binary search terminates.

Code Solutions

def hIndex(citations):
    n = len(citations)
    left, right = 0, n
    while left < right:
        mid = left + (right - left) // 2  # Calculate mid index
        if citations[mid] < n - mid:       # Check if candidate h-index is not met
            left = mid + 1                 # Move to the right half
        else:
            right = mid                    # Move to the left half
    return n - left                       # Final h-index calculation

# Example usage:
print(hIndex([0, 1, 3, 5, 6]))  # Output: 3
print(hIndex([1, 2, 100]))      # Output: 2
← Back to All Questions