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] <= 1000The H-Index measures a researcher's impact based on the number of papers and their citation counts. The goal is to find the maximum value h such that the researcher has at least h papers with h or more citations each.
A common approach is to sort the citation array and then scan it to determine the largest valid h. After sorting, you can compare each position with the number of papers remaining to see whether the citation threshold satisfies the definition. This approach is intuitive and works well for interview scenarios.
An optimized method uses a counting/bucket technique. Instead of sorting, you track how many papers have a certain number of citations and cap values greater than n. By accumulating counts from higher citation values downward, you can efficiently determine when the number of papers meets the h condition.
The sorting solution runs in O(n log n), while the counting strategy can achieve O(n) time with additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting the citations array | O(n log n) | O(1) or O(n) depending on sort |
| Counting / Bucket approach | O(n) | O(n) |
Techdose
Use these hints if you're stuck. Try solving on your own first.
An easy approach is to sort the array first.
What are the possible values of h-index?
A faster approach is to use extra space.
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.
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) since the sorting is in place.
1using System;
2
3public class Solution {
4 public int HIndex(int[] citations) {
5 Array.Sort(citations);
6 Array.Reverse(citations);
7 int n = citations.Length;
8 for (int i = 0; i < n; i++) {
9 if (citations[i] < i + 1) {
10 return i;
11 }
12 }
13 return n;
14 }
15
16 public static void Main(string[] args) {
17 int[] citations = {3, 0, 6, 1, 5};
18 Solution sol = new Solution();
19 Console.WriteLine("H-Index: " + sol.HIndex(citations));
20 }
21}This C# solution sorts the array in descending order and determines the h-index in a manner similar to the other solutions provided.
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.
Time Complexity: O(n + m) where n is citationsSize and m is the maximum citation value, Space Complexity: O(m).
1#include <vector>
#include <iostream>
using namespace std;
int hIndex(vector<int>& citations) {
int n = citations.size();
vector<int> count(n + 1, 0);
for (int c : citations) {
if (c >= n) count[n]++;
else count[c]++;
}
int total = 0;
for (int i = n; i >= 0; i--) {
total += count[i];
if (total >= i) return i;
}
return 0;
}
int main() {
vector<int> citations = {3, 0, 6, 1, 5};
cout << "H-Index: " << hIndex(citations) << endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, H-Index and similar array-based counting problems appear in technical interviews at companies like Amazon, Google, and Meta. They test understanding of sorting, counting techniques, and efficient problem modeling.
The optimal approach often uses a counting or bucket technique. By counting how many papers have each citation value and accumulating from the highest values, you can determine the largest valid h-index in O(n) time.
Sorting arranges citation counts in order, making it easy to check how many papers have at least a certain number of citations. By comparing the index position with remaining papers, you can directly test whether the h-index condition is satisfied.
An array-based bucket or counting structure is useful for the optimized approach. It tracks how many papers fall into each citation range and helps compute the result without sorting.
This C++ solution employs a vector to create a counting array, tracking citation frequencies.