H-Index II
Mahabharata — Vyasa's Academic Index — Find the Highest Impact Score from Sorted Citations
h शोधपत्राः — प्रत्येकं h-बार उद्धृत। अधिकतमः h — विद्वत्ता की मान्यता॥
*h papers — each cited at least h times. Maximum such h — recognition of scholarship.*
The Story
The H-Index is the maximum h such that at least h papers have ≥ h citations. Given a sorted (ascending) citations array, find H-Index in O(log n).
For `citations = [0,1,3,5,6]` (n=5): h=3 (3 papers have ≥3 citations: [3,5,6]).
**Binary search on h directly:** - For a given h: we need at least h papers with ≥h citations - In a sorted array, the last h papers are citations[n-h..n-1] - These last h papers each have ≥h citations iff `citations[n-h] >= h`
```java int left=0, right=n; while (left < right) { int mid = (left+right+1)/2; // Upper mid (ceiling) if (citations[n-mid] >= mid) left=mid; // h=mid is valid, try larger else right=mid-1; } return left; ```
**Why upper mid `(left+right+1)/2`?** When we increase left=mid, we need mid to be able to equal left+1 when left+1==right. Using upper mid prevents infinite loops in this pattern.
Trace `[0,1,3,5,6]`, n=5: - left=0,right=5,mid=3: citations[5-3]=citations[2]=3 >= 3 ✓ → left=3 - left=3,right=5,mid=4: citations[5-4]=citations[1]=1 >= 4? No → right=3 - left==right=3 → return 3 ✓
The Linear H-Finder
Try h from n down to 0. First h where citations[n-h] >= h. O(n).
public int hIndexBruteForce(int[] citations) {
int n = citations.length;
for (int h = n; h >= 1; h--)
if (citations[n-h] >= h) return h;
return 0;
}Vyasa's Upper-Mid Binary Search
public int hIndex(int[] citations) {
int n = citations.length, left = 0, right = n;
while (left < right) {
int mid = (left + right + 1) / 2; // Upper mid
if (citations[n - mid] >= mid) left = mid;
else right = mid - 1;
}
return left;
}Step-by-Step Walkthrough
[0], n=1 left=0,right=1,mid=1: citations[0]=0>=1? No → right=0 Return 0 ✅ (no papers with ≥1 citation)
Deep Insight
**Why upper mid (`(l+r+1)/2`)?** When `left = mid` (not `left = mid+1`), we must ensure mid can reach `left+1` when `left = right-1`. Floor mid = (l+r)/2 would give `mid = left` when l+r is even, causing infinite loop. Ceiling mid prevents this.
**The condition `citations[n-mid] >= mid`:** The (n-mid)th element is the smallest of the top-mid papers. If it's ≥ mid, all top-mid papers have ≥mid citations → h=mid is valid.
**H-Index meaning:** A researcher with h-index 5 has written at least 5 papers each cited at least 5 times.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Linear scan from n to 0 |
| Optimal | O(log n) | O(1) | Binary search on sorted citations array |
Pattern Recognition
✅ Find maximum h where citations[n-h]>=h ✅ Use upper mid: (left+right+1)/2 ✅ Feasible: left=mid (try larger h) ✅ Infeasible: right=mid-1 **LeetCode Trigger Phrases:** → "h-index" in sorted citations array → Maximum h where at least h papers have ≥h citations → O(log n) on pre-sorted array
Bhagavad Gita 18.42
ज्ञानं विज्ञानमास्तिक्यं ब्रह्मकर्म स्वभावजम्।
Knowledge, realization, and faith — these are the natural duties of the learned.
Connection: The H-Index measures the self-consistent depth of scholarly impact — h papers each cited at least h times. It is not the absolute maximum citations, nor merely the number of papers, but their mutual corroboration. Like the Gita's teaching that knowledge, its realization, and one's faith must all be consistent and mutually sustaining, the H-Index finds the maximum self-sustaining level of scholarly influence.