algoadvance

Leetcode 275. H

Problem Statement

Given an array of integers citations sorted in ascending order (each integer represents the number of citations a researcher has received for their paper), return the researcher’s h-index.

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.

You must write an algorithm that runs in O(log N) time.

Example 1:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 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,2,100]
Output: 2

Constraints:

Clarifying Questions

  1. Q: Is the array guaranteed to be sorted in ascending order as given? A: Yes, the array citations is always sorted in non-decreasing order.

  2. Q: Can the array contain duplicate citation values? A: Yes, duplicate values can be present in the array.

  3. Q: Is it possible for all values in citations to be zero? A: Yes, it is possible, and in such cases, the h-index would be 0.

Strategy

To solve this problem within O(log N) time complexity, we can use a binary search algorithm. The goal is to find the maximal h such that there are at least h papers with h or more citations.

Here’s a step-by-step approach:

  1. Initialize left to 0, and right to n - 1.
  2. Use binary search to find the h-index:
    • Calculate the middle point mid = left + (right - left) / 2.
    • Check if citations[mid] is a valid h-index:
      • If n - mid (number of papers with at least mid citations) is greater than or equal to citations[mid], move the search to the right half by setting left to mid + 1.
      • Otherwise, move the search to the left half by setting right to mid - 1.
  3. Continue this until left exceeds right.
  4. The maximum valid h will be n - left after breaking out of the loop.

This way, we ensure the solution works efficiently in O(log N) time.

Code

public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return n - left;
    }
}

Time Complexity

This solution meets the problem’s constraints and ensures an efficient runtime.

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