Log inSign up
mediumLeetCodeNot Started

H-Index II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Sorted Citations:

Input: citations = [0, 1, 3, 5, 6]
Output: 3
Explanation: [0, 1, 3, 5, 6] means the researcher has 5 papers. 3 papers have at least 3 citations each (3, 5, 6) and the remaining 2 have no more than 3 citations each. So h-index is 3.

Example 2 · Single Element Zero:

Input: citations = [0]
Output: 0
Explanation: The single paper has 0 citations, so h-index is 0.

Example 3 · All High Citations:

Input: citations = [100, 100, 100]
Output: 3
Explanation: All 3 papers have at least 3 citations, so h-index is 3.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • H-Index I fundamentals
  • Binary Search on monotonic conditions
  • Understanding reverse index mapping (N - mid)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Leverage pre-sorted array structure to replace linear scans with Binary Search.
  • Formulate the monotonic predicate: citations[mid] >= N - mid.
  • Derive the final answer from binary search pointers: N - low.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If citations[mid] >= N - mid -> Search left: high = mid - 1.
  • If citations[mid] < N - mid -> Search right: low = mid + 1.
  • Return N - low.

Connected Patterns:

H-Index IBinary Search on ThresholdSearch Insert Position

1. Reverse Linear Scan (Brute Force)

Intuition

Since citations is already sorted ascendingly, at any index i there are exactly n - i papers with at least citations[i] citations. We scan from i = 0 to n - 1. The first index i where citations[i] >= n - i gives the H-index n - i.

When to apply: Use to understand the sorted property relationship before utilizing binary search.

All Suffixes Verification (O(N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Paper 4 has 6 citations, which supports h = 1
Visual state
Values and pointers at this exact step
pointers
S
0
1
3
5
6
0
1
2
3
4
↑ h=1
Variables at this step
h
1
citations
6
bestH
1
Check / comparison
Suffix of size 1: citations[4] = 6 >= 1
Decision / next transition
Valid for h = 1. Track bestH = 1.
Why this step matters

Paper 4 has 6 citations, which supports h = 1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int hIndex(int[] citations) {
4 int n = citations.length;
5 for (int i = 0; i < n; i++) {
6 if (citations[i] >= n - i) {
7 return n - i;
8 }
9 }
10 return 0;
11 }
12 }
13
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] citations = {0, 1, 3, 5, 6};
17 System.out.println("H-Index: " + sol.hIndex(citations));
18 }
19}

Time & Space Complexity

  • Time complexity: O(n) — A single linear scan through the n elements takes O(n) time.
  • Space complexity: O(1) — No extra memory is allocated.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Binary Search with Early Exit (Better)

Intuition

Since the array is sorted, we can search the index space with binary search. If citations[mid] == n - mid, we immediately know that exactly n - mid papers have >= n - mid citations, so n - mid is optimal. If citations[mid] < n - mid, we must move right (low = mid + 1). Otherwise, we move left (high = mid - 1).

When to apply: Use when you want logarithmic search with early termination when citations[mid] exactly equals n - mid.

Right-to-Left Linear Scan (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Scanning from right to left tests candidates h = 1, 2, 3
Visual state
Values and pointers at this exact step
pointers
S
0
1
3
5
6
0
1
2
3
4
↑ i=4
Variables at this step
i
4
h
1
Check / comparison
i = 4: citations[4] = 6 >= n - i (1)
Decision / next transition
Current h candidate = 1.
Why this step matters

Scanning from right to left tests candidates h = 1, 2, 3...

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int hIndex(int[] citations) {
4 int n = citations.length;
5 int low = 0, high = n - 1;
6 while (low <= high) {
7 int mid = low + (high - low) / 2;
8 if (citations[mid] == n - mid) {
9 return n - mid;
10 } else if (citations[mid] < n - mid) {
11 low = mid + 1;
12 } else {
13 high = mid - 1;
14 }
15 }
16 return n - low;
17 }
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 int[] citations = {0, 1, 3, 5, 6};
23 System.out.println("H-Index: " + sol.hIndex(citations));
24 }
25}

Time & Space Complexity

  • Time complexity: O(log n) — Binary search halves the search space at each iteration, taking O(log n) comparisons.
  • Space complexity: O(1) — O(1) memory for low, high, and mid index pointers.

3. Binary Search for First Valid Index (Optimal)

Intuition

We seek the smallest index i such that citations[i] >= n - i. For all indices j >= i, the condition citations[j] >= n - j also holds because citations[j] is non-decreasing and n - j is non-increasing. Hence the predicate citations[mid] >= n - mid is monotonic (False, ..., False, True, ..., True). Binary search finds the transition point in O(log n) time.

When to apply: Use as the canonical optimal solution whenever the input citations array is guaranteed to be sorted.

Binary Search on Sorted Citations (O(log N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
When citations[mid] >= n - mid, this index qualifies
Visual state
Values and pointers at this exact step
pointers
S
0
1
3
5
6
0
↑ low
1
2
↑ mid
3
4
↑ high
Variables at this step
low
0
mid
2
high
4
citations
3
suffixCount
3
Check / comparison
low = 0, high = 4 -> mid = 2. citations[2] = 3. Suffix count n - mid = 5 - 2 = 3
Decision / next transition
citations[mid] == n - mid (3 == 3)! Exact boundary found: high = mid - 1 = 1.
Why this step matters

When citations[mid] >= n - mid, this index qualifies. Search left to find if an even earlier index qualifies (which would yield a larger H-index).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int hIndex(int[] citations) {
4 int n = citations.length;
5 int low = 0, high = n - 1;
6 while (low <= high) {
7 int mid = low + (high - low) / 2;
8 if (citations[mid] >= n - mid) {
9 high = mid - 1;
10 } else {
11 low = mid + 1;
12 }
13 }
14 return n - low;
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] citations = {0, 1, 3, 5, 6};
21 System.out.println("H-Index: " + sol.hIndex(citations));
22 }
23}

Time & Space Complexity

  • Time complexity: O(log n) — The search space [0, n-1] is halved each step, resulting in exactly ceil(log2(n)) iterations.
  • Space complexity: O(1) — O(1) auxiliary space using pointer variables low, high, and mid.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear ScanO(N)O(1)Scan from left to right, return N - i at the first index where citations[i] >= N - i.Iterates one by one across sorted array.
2.Better — Suffix Reverse ScanO(N)O(1)Scan backwards from index N-1 maintaining paper count.Linear inspection.
3.Optimal — Binary SearchOptimalO(log N)O(1)Binary search for the first index mid where citations[mid] >= N - mid.None; optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All zeroes: citations = [0, 0, 0] -> low ends at 3, returns 3 - 3 = 0.
  • All huge numbers: citations = [10, 20, 30] -> low ends at 0, returns 3 - 0 = 3.
  • Single element array: citations = [0] returns 0, citations = [5] returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for H-Index II?

2.Why is the brute force approach suboptimal for large inputs in H-Index II?

3.Which data structure or technique enables the optimal solution for H-Index II?

Back to DSA Sheet