Scale Engineer

H-Index

Med
#0261Time: O(n²) where n is the length of citations arraySpace: O(1) constant space3 companies
Algorithms
SortingCounting Sort
Data structures
Array
Companies
ByteDanceNvidiaZoox

Prompt

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.length
  • 1 <= n <= 5000
  • 0 <= 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

  1. Initialize maxHIndex = 0
  2. For h from 1 to n:
    • Count papers with citations >= h
    • If count >= h, update maxHIndex
  3. Return maxHIndex

Walkthrough

For each possible h-index value h from 1 to n:

  1. Count the number of papers that have citations >= h
  2. If the count is >= h, update the maximum h-index
  3. 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

Solutions

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;      }    }  }}

Video 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.

← Previous

Previous problem

Next →

Next problem