H-Index
MedPrompt
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] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
Check each possible h-index value from 1 to n by counting papers with citations greater than or equal to the current h-index value.
Algorithm
- Initialize maxHIndex = 0
- For h from 1 to n:
- Count papers with citations >= h
- If count >= h, update maxHIndex
- Return maxHIndex
Walkthrough
For each possible h-index value h from 1 to n:
- Count the number of papers that have citations >= h
- If the count is >= h, update the maximum h-index
- Continue until we've checked all possible values
public int hIndex(int[] citations) { int n = citations.length; int maxHIndex = 0; for (int h = 1; h <= n; h++) { int count = 0; for (int citation : citations) { if (citation >= h) { count++; } } if (count >= h) { maxHIndex = Math.max(maxHIndex, h); } } return maxHIndex;}Complexity
Time
O(n²) where n is the length of citations array
Space
O(1) constant space
Trade-offs
Pros
Simple to understand and implement
No additional space required
Works with unsorted input
Cons
Not efficient for large inputs
Performs unnecessary iterations
Sort the citations array in descending order and find the largest index where citations[i] >= i+1.
Algorithm
- Sort array in descending order
- For i from 0 to n-1:
- If citations[i] < i+1, return i
- Return n if no solution found
Walkthrough
- Sort the array in descending order
- Find the largest index i where citations[i] >= i+1
- The h-index will be i+1
public int hIndex(int[] citations) { Arrays.sort(citations); int n = citations.length; // Convert to descending order problem for (int i = 0; i < n/2; i++) { int temp = citations[i]; citations[i] = citations[n-1-i]; citations[n-1-i] = temp; } for (int i = 0; i < n; i++) { if (citations[i] < i + 1) { return i; } } return n;}Complexity
Time
O(n log n) due to sorting
Space
O(1) if in-place sorting is used
Trade-offs
Pros
More efficient than brute force
Easy to understand
Works well for most inputs
Cons
Modifies input array
Still not optimal
Requires sorting
Use counting sort technique to count papers for each citation number and then find the h-index by accumulating counts from highest to lowest.
Algorithm
- Create count array of size n+1
- Count papers for each citation
- Accumulate counts from highest to lowest
- Return first i where accumulated count >= i
Walkthrough
- Create a count array to store frequency of citations
- Count papers for each citation number
- Accumulate counts from highest to lowest until we find h-index
public int hIndex(int[] citations) { int n = citations.length; int[] count = new int[n + 1]; // Count papers for each citation number for (int citation : citations) { if (citation >= n) { count[n]++; } else { count[citation]++; } } // Find h-index by accumulating counts int total = 0; for (int i = n; i >= 0; i--) { total += count[i]; if (total >= i) { return i; } } return 0;}Complexity
Time
O(n) where n is the length of citations array
Space
O(n) for the count array
Trade-offs
Pros
Most efficient solution
Doesn't modify input array
Works in linear time
Cons
Uses extra space
Might not be intuitive at first
Solutions
Solution
class Solution {public int hIndex(int[] citations) { int n = citations.length; int[] cnt = new int[n + 1]; for (int x : citations) { ++cnt[Math.min(x, n)]; } for (int h = n, s = 0;; --h) { s += cnt[h]; if (s >= h) { return h; } } }}class Solution {public: int hIndex(vector<int> &citations) { int n = citations.size(); int cnt[n + 1]; memset(cnt, 0, sizeof(cnt)); for (int x : citations) { ++cnt[min(x, n)]; } for (int h = n, s = 0;; --h) { s += cnt[h]; if (s >= h) { return h; } } }};class Solution: def hIndex(self, citations: List[int]) -> int: n = len(citations) cnt = [0] * (n + 1) for x in citations: cnt[min(x, n)] += 1 s = 0 for h in range(n, - 1, - 1): s += cnt[h] if s >= h: return hVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.