LeetCode 275: H-Index II

Explanation

To solve this problem in logarithmic time, we can use binary search. We will search for the h-index value within the range of 0 to n, where n is the total number of papers. We can adjust the range based on the citations received for each paper. If the number of papers with citations greater than or equal to a certain value is greater than or equal to that value, we update our h-index candidate. We continue this process until we find the maximum h-index value.

• Time Complexity: O(log n) where n is the number of papers.
• Space Complexity: O(1)

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;
    }
}