H-Index — Solution in Python, Java & C++
H-Index 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 is a medium coding problem on arrays, sorting and counting sort, asked in Amazon, Google, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Counting Sort
- Asked at: Amazon, Google, Meta, Bloomberg
- 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
Given an array citations where citations[i] is the number of citations a researcher's i-th paper received, return their h-index.
The h-index is the largest h such that the researcher has published at least h papers that have each been cited at least h times.
Example 1
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: Three papers have at least 3 citations each; there are not four papers with at least 4.
Example 2
Input: citations = [1,3,1]
Output: 1
Example 3
Input: citations = [0,0]
Output: 0
Constraints
1 <= citations.length <= 400 <= citations[i] <= 1000
Follow-up: Sorting makes it O(n log n). Counting makes it O(n).
Hints for H-Index
Hint 1
Sort the citations in descending order.
Hint 2
After sorting, the paper at 0-based index
iis the (i + 1)-th best; if it still hasi + 1citations, an h-index ofi + 1is achievable.Hint 3
Take the largest such
i + 1— the condition can turn on and off, so do not stop at the first failure without checking.
How to solve H-Index
Sort descending; the paper at 0-based index i is the (i + 1)-th best, and if it has at least i + 1 citations then h = i + 1 is achievable. Take the largest such i + 1.
Approach
- Sort citations in descending order.
- For each
i, ifordered[i] >= i + 1, seth = i + 1. - Return
h.
Why it works
In descending order the first i + 1 papers all have at least ordered[i] citations, so the condition certifies h = i + 1. The condition is monotone — once it fails it stays failed — so the last success is the maximum.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- A bucket count over
0..ngives O(n). - An all-zero array has h-index 0.
Reference solution
Python
def hIndex(citations):
ordered = sorted(citations, reverse=True)
h = 0
for i, c in enumerate(ordered):
if c >= i + 1:
h = i + 1
return hJava
public static int hIndex(int[] citations) {
int[] ordered = Arrays.copyOf(citations, citations.length);
Arrays.sort(ordered);
int n = ordered.length;
int h = 0;
for (int i = 0; i < n; i++) {
if (ordered[n - 1 - i] >= i + 1) h = i + 1;
}
return h;
}C++
int hIndex(vector<int>& citations) {
vector<int> ordered = citations;
sort(ordered.begin(), ordered.end(), greater<int>());
int h = 0;
for (int i = 0; i < (int) ordered.size(); i++) {
if (ordered[i] >= i + 1) h = i + 1;
}
return h;
}JavaScript
var hIndex = function(citations) {
const ordered = citations.slice().sort(function(a, b) { return b - a; });
let h = 0;
for (let i = 0; i < ordered.length; i++) {
if (ordered[i] >= i + 1) h = i + 1;
}
return h;
};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 · Sorting Algorithms