Log inSign up
mediumLeetCodeNot Started

H-Index

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, 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 · Standard Case with 5 Papers:

Input: citations = [3, 0, 6, 1, 5]
Output: 3
Explanation: The researcher has 5 papers with citations 3, 0, 6, 1, 5. There are 3 papers with at least 3 citations each (3, 6, 5), and the remaining two have <= 3 citations each. So h-index is 3.

Example 2 · All Low Citations:

Input: citations = [1, 3, 1]
Output: 1
Explanation: The researcher has at least 1 paper with >= 1 citation. (For h=2, only 1 paper has >= 2 citations, which is not enough).

Example 3 · Zero Citations:

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

Constraints:

  • 1 <= citations.length <= 105
  • 0 <= citations[i] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Understanding the formal definition of H-Index
  • Counting sort and bucket accumulation
  • Prefix/suffix sum concepts

What You'll Learn

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

  • Recognize when an answer is strictly bounded by input size N.
  • Master the bucket clamp technique: mapping all values >= N into bucket[N].
  • Compare sorting vs counting sort paradigms.

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 the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

H-Index II (Sorted Array Binary Search)Counting SortBucket Array Aggregation

1. Exhaustive Candidate Search (Brute Force)

Intuition

By definition, the H-index cannot exceed the total number of papers n. We can test candidate values h from n down to 0. For each candidate h, we iterate through the entire citations array and count how many papers have citations >= h. The first candidate h where count >= h is the maximum possible H-index.

When to apply: Use to understand the mathematical definition of H-index before optimizing with sorting.

Candidate Threshold Scan (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
A valid H-index requires at least h papers with >= h citations
Visual state
Values and pointers at this exact step
pointers
S
3
0
6
1
5
0
1
2
3
4
↑ h=5
Variables at this step
testH
5
qualifyingCount
2
valid
false
Check / comparison
Test candidate h = 5: Count papers with citations >= 5
Decision / next transition
Only 2 papers (6 and 5) have >= 5 citations. 2 < 5 -> h = 5 is INVALID.
Why this step matters

A valid H-index requires at least h papers with >= h citations.

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 h = n; h >= 1; h--) {
6 int count = 0;
7 for (int c : citations) {
8 if (c >= h) count++;
9 }
10 if (count >= h) return h;
11 }
12 return 0;
13 }
14 }
15
16 public static void main(String[] args) {
17 Solution sol = new Solution();
18 int[] citations = {3, 0, 6, 1, 5};
19 System.out.println("H-Index: " + sol.hIndex(citations));
20 }
21}

Time & Space Complexity

  • Time complexity: O(n^2) — Testing each candidate h from n down to 0 takes O(n) trials, and each trial scans the n papers.
  • Space complexity: O(1) — Only constant extra variables (candidate h and count) are maintained.

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. Sorting Descending (Better)

Intuition

When sorted in descending order: citations[0] >= citations[1] >= ... >= citations[n-1]. At index i, there are exactly i + 1 papers with at least citations[i] citations. If citations[i] >= i + 1, then an H-index of at least i + 1 is guaranteed. The moment citations[i] < i + 1, the maximum valid H-index is i.

When to apply: Use when an O(n log n) solution is acceptable and in-place sorting is permitted.

Sort Ascending + Linear Suffix Check (O(N log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sorted order enables direct suffix counting
Visual state
Values and pointers at this exact step
pointers
S
0
1
3
5
6
0
↑ sorted
1
2
3
4
Variables at this step
sorted
[0,1,3,5,6]
n
5
Check / comparison
Sort array ascending: [0, 1, 3, 5, 6]. n = 5
Decision / next transition
At index i, the number of papers with citations >= citations[i] is exactly (n - i).
Why this step matters

Sorted order enables direct suffix counting.

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

Time & Space Complexity

  • Time complexity: O(n log n) — Sorting n citations takes O(n log n) time, followed by a single O(n) linear scan.
  • Space complexity: O(1) or O(n) — O(1) extra space if sorting in-place, or O(n) depending on the language's sorting algorithm.

3. Counting Sort / Bucket Array (Optimal)

Intuition

Since the H-index cannot exceed the total number of papers n, any paper with more than n citations can be treated as having n citations. We allocate an array of buckets of size n + 1. We tally frequencies in O(n) time. Then, scanning backwards from n to 0, we accumulate the running count of papers. The first value of h where runningCount >= h is the optimal H-index.

When to apply: Use to achieve optimal O(n) time complexity by avoiding general comparison-based sorting.

Counting Sort Frequency Buckets (O(N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Paper with 6 citations is placed into bucket 5 because having more than n citations cannot yield H > n
Visual state
Values and pointers at this exact step
pointers
S
1
1
0
1
0
2
0
↑ buckets
1
2
3
4
5
Variables at this step
buckets
[1,1,0,1,0,2]
totalPapers
0
Check / comparison
Build frequency buckets [0..5] (capping citations > 5 into bucket 5)
Decision / next transition
Buckets: count[0]=1, count[1]=1, count[2]=0, count[3]=1, count[4]=0, count[5]=2.
Why this step matters

Paper with 6 citations is placed into bucket 5 because having more than n citations cannot yield H > n.

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[] buckets = new int[n + 1];
6 for (int c : citations) {
7 if (c >= n) {
8 buckets[n]++;
9 } else {
10 buckets[c]++;
11 }
12 }
13 int total = 0;
14 for (int h = n; h >= 0; h--) {
15 total += buckets[h];
16 if (total >= h) {
17 return h;
18 }
19 }
20 return 0;
21 }
22 }
23
24 public static void main(String[] args) {
25 Solution sol = new Solution();
26 int[] citations = {3, 0, 6, 1, 5};
27 System.out.println("H-Index: " + sol.hIndex(citations));
28 }
29}

Time & Space Complexity

  • Time complexity: O(n) — One O(n) pass to populate the bucket array of size n + 1, and one O(n) pass to accumulate sums from n down to 0.
  • Space complexity: O(n) — O(n) auxiliary memory for the bucket array of size n + 1.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Test every possible h from N down to 0 and count how many papers have >= h citations.Iterating through the entire array for each candidate h.
2.Better — SortingO(N log N)O(1)Sort citations in ascending order. At index i, there are (N - i) papers with >= citations[i] citations.Sorting overhead.
3.Optimal — Bucket CountingOptimalO(N)O(N)Bucket citations into array of size N+1. Accumulate papers from N down to 0.None; industry-standard 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] -> returns 0.
  • Single paper with high citation: citations = [100] -> returns 1 (since total papers = 1).
  • All papers with huge citations: citations = [100, 200, 300] -> returns 3.

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?

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

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

Back to DSA Sheet