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:
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.length1 <= n <= 50000 <= citations[i] <= 1000Problem Overview: You are given an array where citations[i] represents the number of citations for a researcher's i-th paper. The H-Index is the largest value h such that the researcher has at least h papers with h or more citations each. The task is to compute that maximum h.
Approach 1: Sorting Approach (O(n log n) time, O(1) extra space)
Sort the citations and determine how many papers have at least a certain citation count. After sorting in ascending order, iterate through the array and treat each position as a candidate H value. If there are n - i papers remaining and citations[i] >= n - i, then n - i is a valid H-Index. The key idea: the sorted order makes it easy to compare the number of remaining papers against the citation threshold. This approach relies on basic Array traversal and Sorting. It’s simple to reason about and usually the first implementation developers write.
Approach 2: Counting Sort / Bucket Approach (O(n) time, O(n) space)
The H-Index cannot exceed the number of papers n. Instead of sorting, create a frequency bucket where index i counts how many papers have exactly i citations. Any citation value greater than n is capped into bucket n. Then iterate from the highest bucket downward while maintaining a running total of papers with at least that many citations. Once the cumulative count becomes greater than or equal to the current index, that index is the H-Index. This eliminates sorting and achieves linear time using a Counting Sort-style frequency array.
Recommended for interviews: The sorting approach is the most commonly discussed solution because it is easy to implement and clearly demonstrates the definition of H-Index. Interviewers often accept this O(n log n) approach first. The counting bucket optimization shows stronger algorithmic thinking since it leverages the constraint that H cannot exceed n, reducing the runtime to O(n). Explaining both approaches demonstrates solid understanding of tradeoffs between sorting-based solutions and frequency counting techniques.
This approach uses sorting to calculate the h-index. The idea is to sort the array of citations in descending order. Then, find the maximum number h such that there are h papers with at least h citations. This can be efficiently determined by iterating over the sorted array.
The code sorts the array in descending order, then iterates through it to find the largest h such that citations[h] >= h. If no such h is found, it returns the size of the array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) since the sorting is in place.
Given the constraints where citation counts do not exceed 1000 and the number of papers is at most 5000, a counting sort or bucket sort can be used. This approach involves creating a frequency array to count citations. Then traverse the frequency array to compute the h-index efficiently.
This C implementation uses a frequency array to count papers for citation values. It accumulates from the back (high values) to find the point where the count matches or exceeds the index.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m) where n is citationsSize and m is the maximum citation value, Space Complexity: O(m).
| Approach | Complexity |
|---|---|
| Sorting Approach | Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) since the sorting is in place. |
| Counting Sort Approach | Time Complexity: O(n + m) where n is citationsSize and m is the maximum citation value, Space Complexity: O(m). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting | O(n log n) | O(1) or O(log n) | General solution. Easy to implement and explain in interviews. |
| Counting Sort / Bucket | O(n) | O(n) | When you want optimal linear time and can use extra memory for frequency buckets. |
H index | Leetcode #274 • Techdose • 53,608 views views
Watch 9 more video solutions →Practice H-Index with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor