Is H-Index II easy or hard?

H-Index II is generally classified as a medium difficulty problem. The challenge lies in recognizing that the sorted array creates a monotonic condition that can be solved with binary search instead of scanning every element.

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

Use binary search on the sorted citations array. At index mid, compare citations[mid] with n - mid (the number of papers remaining). If citations[mid] >= n - mid, search the left half; otherwise search the right half. The final answer becomes n - left after the search converges.

What is the best approach for H-Index II?

Binary search is the optimal approach because the citations array is already sorted. You search for the smallest index i where citations[i] >= n - i. This reduces the runtime to O(log n) while using O(1) additional space.

What data structure is used in H-Index II?

The core data structure is a sorted array of citation counts. The optimized solution combines array indexing with binary search to locate the boundary where the H-index condition becomes valid.

What is the time complexity of H-Index II?

The optimal binary search solution runs in O(log n) time with O(1) space. A simpler linear scan approach exists with O(n) time and constant space, which still works efficiently for moderate input sizes.

H-Index II Python or Java solution approach?

Both Python and Java implementations typically follow the same binary search logic. Maintain left and right pointers, compute mid, compare citations[mid] with n - mid, and adjust the search range until the correct boundary index is found.

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

Binary search problems similar to H-Index II frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. The problem tests your ability to recognize monotonic conditions and apply binary search beyond simple element lookup.

Description Hints 1 Solution Video 17:37

275. H-Index II

Medium40.0% acceptance1 company

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

You must write an algorithm that runs in logarithmic time.

Example 1:

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

Constraints:

n == citations.length
1 <= n <= 10⁵
0 <= citations[i] <= 1000
citations is sorted in ascending order.

Asked at 1 company

Topics

Array Binary Search

Hints open one at a time

Hint 1

Expected runtime complexity is in O(log n) and the input is sorted.

17:37

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

Open solution