H-Index II

LeetCode 275 | Difficulty: Medium

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 non-descending order, return the researcher's h-index.

According to the definition of h-index on Wikipedia: 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.

You must write an algorithm that runs in logarithmic 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:

- `n == citations.length`

- `1 <= n <= 10^5`

- `0 <= citations[i] <= 1000`

- `citations` is sorted in **ascending order**.

Topics: Array, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 168 ms)

Metric	Value
Runtime	168 ms
Memory	39.7 MB
Date	2022-01-17

Solution

public class Solution {
    public int HIndex(int[] citations) {
        int len = citations.Length;
    int lo=0, hi = len-1;
    while(lo <=hi)
    {
        int mid = (hi+lo)/2;
        if(citations[mid] == len-mid)
        {
            return len-mid;
        }
        else if(citations[mid] < len-mid)
        {
            lo = mid+1;
        }
        else
        {
             hi = mid-1;
        }
    }
    
    return len-lo;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Expected runtime complexity is in O(log n) and the input is sorted.