Is H-Index easy or hard?

H-Index is generally classified as a medium-level problem. Understanding the definition and implementing the sorting approach is straightforward, but recognizing the bucket counting optimization requires stronger algorithmic insight.

How to solve H-Index in O(n)?

Use a bucket counting strategy. Create an array of size n+1 where index i stores how many papers have exactly i citations (values greater than n are capped at n). Traverse the bucket array from n down to 0 while maintaining a cumulative count of papers. The first index where the cumulative count becomes at least the index is the H-index.

What is the best approach for H-Index?

The most optimal approach uses a counting sort or bucket counting technique with O(n) time and O(n) space. It works by grouping citation counts into buckets from 0 to n (where n is the number of papers) and scanning backward to find the largest h where at least h papers have ≥ h citations. This avoids sorting the entire array.

What data structure is used in H-Index?

The core data structure is an array. The basic method sorts the array of citation counts, while the optimal method uses an additional bucket array to store frequency counts. No complex structures like trees or heaps are required.

What is the time complexity of H-Index?

Two common complexities appear in solutions. The straightforward sorting approach runs in O(n log n) time because the citations array must be ordered first. The optimized counting sort approach achieves O(n) time by using a frequency bucket array and scanning it once.

Is there a Python or Java solution for H-Index?

Yes. The sorting approach can be implemented in a few lines using built-in sort functions in Python, Java, C++, or JavaScript. The linear-time version uses an integer array for buckets and works similarly across languages, making it easy to translate between Python, Java, and C++.

Is H-Index asked at Google, Amazon, or Meta interviews?

H-Index appears in interview preparation sets for companies like Amazon, Google, and Meta because it tests reasoning about arrays, counting strategies, and translating a mathematical definition into code. The optimal bucket approach also evaluates whether candidates can improve beyond a straightforward sorting solution.

Description Hints 3 Solution Video 2:31

274. H-Index

Medium41.8% acceptance8 companies

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i^th paper, 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.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 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,3,1]
Output: 1

Constraints:

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

Asked at 8 companies

Bloomberg

Google Amazon Microsoft Apple NVIDIA Meta LinkedIn

Topics

Hints open one at a time

Hint 1

An easy approach is to sort the array first.

Hint 2

What are the possible values of h-index?

Hint 3

A faster approach is to use extra space.

2:31

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution