Problem Overview

You are given an integer array citations sorted in ascending order, where citations[i] represents the number of citations a researcher received for their i-th paper.
You need to compute the researcher’s h-index.

The h-index is defined as the maximum value h such that the researcher has at least h papers with at least h citations each.

You must solve this problem in O(log n) time complexity.

Example 1:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: 
There are 3 papers with at least 3 citations each: [3,5,6].

Example 2:

Input: citations = [1,2,100]
Output: 2
Explanation:
There are 2 papers with at least 2 citations each: [2,100].

---

Intuition / Approach

This is an optimized version of the H-Index problem (LeetCode 274).
Because the array is sorted in ascending order, we can use binary search to find the h-index efficiently.

Let:

• n = total number of papers
• The condition for h-index at position i is:
  citations[i] >= n – i

Why?
Because there are (n - i) papers that have at least citations[i] citations (since the array is sorted ascendingly).

We need to find the smallest index i that satisfies this condition, and then compute:

h = n - i

---

Step-by-Step Example

For citations = [0, 1, 3, 5, 6], n = 5

Index (i)	citations[i]	Papers with ≥ citations[i]	n – i	Condition	Valid?
0	0	5	5	0 >= 5	No
1	1	4	4	1 >= 4	No
2	3	3	3	3 >= 3	Yes
3	5	2	2	5 >= 2	Yes
4	6	1	1	6 >= 1	Yes

The first valid index is 2.
Hence, h = n - i = 5 - 2 = 3.

---

Algorithm Explanation

1. Initialize left = 0, right = n - 1.
2. While left <= right:
   • Compute mid = left + (right - left) / 2
   • If citations[mid] == n - mid, we have found the exact h-index → return citations[mid].
   • If citations[mid] < n - mid, move left to mid + 1 (need higher citation count).
   • Else move right to mid - 1 (too many citations, move left).
3. After the loop, the correct h-index is n - left.

---

Java Code Implementation

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; // exact match
            } else if (citations[mid] < n - mid) {
                left = mid + 1; // need more citations
            } else {
                right = mid - 1; // move to lower citations
            }
        }

        return n - left;
    }
}

---

Dry Run Example

Input: [0, 1, 3, 5, 6]

Step	left	right	mid	citations[mid]	n – mid	Action
1	0	4	2	3	3	Found → return 3

Output: 3

---

Time and Space Complexity

Complexity	Description
Time Complexity	O(log n) due to binary search
Space Complexity	O(1) — no extra data structures used

---

Alternative Approach (Linear Scan)

You could also use a linear approach (O(n)) by scanning from the end of the array and checking citations[i] >= n - i.
However, since the problem explicitly requires O(log n), the binary search method is preferred.

---

Key Takeaways

• The h-index definition ensures we look for the largest h satisfying the condition.
• When the array is sorted, the formula citations[i] >= n - i enables an efficient binary search.
• After binary search ends, n - left gives the maximum valid h-index.