Skip to main content
Talentd

H-Index II - Solution & Explanation

MediumArrayBinary Search16 min readAsked at: Meta
Practice this problem

Problem Statement

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith 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 <= 105
  • 0 <= citations[i] <= 1000
  • citations is sorted in ascending order.

Approach Overview

Problem Overview: You receive a sorted array citations where citations[i] represents the number of citations for a research paper. The array is sorted in ascending order. Your goal is to compute the researcher's H-index: the maximum h such that at least h papers have ≥ h citations.

The sorted property changes how you approach the problem compared to the original H-Index problem. Instead of scanning all possible values, you can use the index position to infer how many papers remain on the right side of the array.

Approach 1: Linear Scan from the End (O(n) time, O(1) space)

Start from the end of the sorted array where citation counts are largest. For each index i, the number of papers with at least citations[i] citations equals n - i. Check whether citations[i] >= n - i. The first position that satisfies this condition determines the H-index.

This works because the array is sorted: moving left only decreases citation counts while increasing the number of papers considered. Once the condition becomes true, you’ve found the largest valid H-index. The algorithm simply iterates once across the array, making it easy to implement with constant memory.

This approach is practical when input size is moderate or when code simplicity matters more than theoretical optimality. It relies only on sequential iteration over an array.

Approach 2: Binary Search on Citation Threshold (O(log n) time, O(1) space)

The sorted order enables a classic binary search. Instead of checking every index, search for the smallest index i where citations[i] >= n - i. The value n - i represents how many papers lie to the right (including the current one), which corresponds to a potential H-index candidate.

During the search, compute mid. If citations[mid] >= n - mid, the condition might hold for an even smaller index, so move the right boundary left. Otherwise, move the left boundary right because the citation count is too small to support that many papers.

Once the search converges, the H-index equals n - left. This reduces the complexity from linear to logarithmic time while maintaining constant memory usage. Binary search fits naturally because the condition forms a monotonic boundary across the sorted array.

This solution combines array indexing with binary search logic and is the expected optimal approach in most technical interviews.

Recommended for interviews: Start by explaining the linear scan to demonstrate understanding of the H-index definition. Then optimize using binary search by leveraging the sorted array property. Interviewers typically expect the O(log n) binary search solution because recognizing the monotonic condition shows strong algorithmic reasoning.

Approach 1: Binary Search Approach

Given the array is sorted, we can efficiently search for the h-index using binary search, aiming for logarithmic time complexity. The idea is to use the binary search to find the maximum h such that citations[h] ≥ h.

The C solution defines a function hIndex using binary search to find the h-index. It utilizes a loop to adjust left and right boundaries based on comparison, reducing the search space logarithmically.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n).
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Linear Scan Approach

In this linear scan approach, we traverse the sorted citations list from beginning to end. The goal is to determine the maximum valid h-index by checking citations against their corresponding paper count.

This C implementation uses a simple loop to check each citation's sufficiency against its position in the list, returning the calculated h-index when the condition is satisfied.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Binary Search

We notice that if there are at least x papers with citation counts greater than or equal to x, then for any y \lt x, its citation count must also be greater than or equal to y. This exhibits monotonicity.

Therefore, we use binary search to enumerate h and obtain the maximum h that satisfies the condition. Since we need to satisfy that h papers are cited at least h times, we have citations[n - mid] \ge mid.

The time complexity is O(log n), where n is the length of the array citations. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search Approach

Time Complexity: O(log n).
Space Complexity: O(1).

Linear Scan Approach

Time Complexity: O(n).
Space Complexity: O(1).

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Scan from EndO(n)O(1)When implementation simplicity matters and the array size is manageable
Binary Search on Sorted CitationsO(log n)O(1)Best choice when the citations array is sorted and optimal performance is required

Video Solution

H Index II | Binary search | Leetcode #275 • Techdose • 39,255 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice H-Index II with our built-in code editor and test cases.

Practice on FleetCode
Previous

H-Index