H-Index II — Solution in Python, Java & C++
H-Index II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
H-Index II is a medium coding problem on arrays and binary search, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
citations[i] is the number of citations the researcher's i-th paper received, sorted in ascending order.
The h-index is the largest h such that at least h papers have at least h citations each. Return it in O(log n) time.
Example 1
Input: citations = [0,1,3,5,6]
Output: 3
Explanation: Three papers have at least 3 citations.
Example 2
Input: citations = [1,2,100]
Output: 2
Example 3
Input: citations = [0]
Output: 0
Constraints
1 <= citations.length <= 1000000 <= citations[i] <= 1000citations is sorted in ascending order.
Hints for H-Index II
Hint 1
Counting from the top: the
hmost-cited papers are the lasthof the sorted array.Hint 2
So
hworks exactly whencitations[n - h] >= h.Hint 3
That predicate is monotone in
h, so binary search it.
How to solve H-Index II
With the array sorted ascending, the h most-cited papers are its last h entries, and the weakest of them sits at index n - h. So the test is a single array lookup, and it is monotone in h.
Approach
- Binary search
hover[0, n]. - For a candidate count
mid(meaningh = mid + 1), checkcitations[n - 1 - mid] >= mid + 1. - Move
lopastmidwhen it holds; the finallois the h-index.
Why it works
If h papers each have at least h citations, then h - 1 papers each have at least h - 1 — so feasibility is downward closed and the boundary is unique. Sorting means the weakest of the top h is citations[n - h], which makes the check O(1) and the whole search logarithmic.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
- Off-by-one between
hand the array index is the classic trap —hpapers means indicesn - h … n - 1. - Sorting or counting would be
O(n log n)orO(n), both failing the stated requirement. - An h-index of 0 is legitimate when the best paper has no citations.
Reference solution
Python
from typing import List
def hIndex(citations: List[int]) -> int:
n = len(citations)
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
if citations[n - 1 - mid] >= mid + 1:
lo = mid + 1
else:
hi = mid
return loJava
public static int hIndex(int[] citations) {
int n = citations.length;
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (citations[n - 1 - mid] >= mid + 1) lo = mid + 1; else hi = mid;
}
return lo;
}C++
int hIndex(vector<int>& citations) {
int n = (int) citations.size();
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (citations[n - 1 - mid] >= mid + 1) lo = mid + 1; else hi = mid;
}
return lo;
}JavaScript
var hIndex = function(citations) {
var n = citations.length;
var lo = 0, hi = n;
while (lo < hi) {
var mid = Math.floor((lo + hi) / 2);
if (citations[n - 1 - mid] >= mid + 1) lo = mid + 1; else hi = mid;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search