medium H-Index

Problem Statement

Given an integer array citations where citations[i] represents the number of times a researcher's i^th paper has been cited, return the researcher's h-index.

The h-index is defined as the maximum number h such that the researcher has h papers with at least h citations each.

Examples

Example 1

• Input: citations = [4, 3, 0, 1, 5]
• Expected Output: 3
• Justification: The researcher has 3 papers with at least 3 citations each.

Example 2

• Input: citations = [10, 8, 5, 4, 3, 7, 2, 1]
• Expected Output: 4
• Justification: The researcher has 4 papers with at least 4 citations each.

Example 3

• Input: citations = [0, 1, 2, 3, 4]
• Expected Output: 2
• Justification: The researcher has 2 papers with at least 2 citations each.

Constraints:

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

Solution

To solve this problem, we use an array to count the number of papers with a given number of citations. This approach helps us determine the h-index efficiently. First, we count how many papers have each citation count, capping at the total number of papers. Then, we traverse the array from the highest possible citation count to the lowest, summing the counts until the sum is at least as large as the current index. This index represents the h-index.

This approach works well because it avoids the need to sort the array, which is the bottleneck in the traditional solution. By counting citations directly, we reduce the time complexity to O(n), making the solution faster and more scalable.

Step-by-step Algorithm

• Initialize: Create an array papers of size n + 1 to count papers for each citation number, where n is the length of the input array citations.
• Count Papers: Iterate through each citation in citations. For each citation count c, increment the corresponding index in papers by one. If c is greater than n, increment papers[n] instead.
• Find h-index:
  • Start from the highest possible citation count (n).
  • Initialize a sum variable s to the count of papers with the highest citation.
  • Iterate downwards through the papers array. For each index k, if s is less than or equal to k, add the count at the current index to s and move to the next lower index.
  • Return the current index k when s is greater than or equal to k.

Algorithm Walkthrough

Input: citations = [10, 8, 5, 4, 3, 7, 2, 1]

• Step 1: Initialize papers array: [0, 0, 0, 0, 0, 0, 0, 0, 0]
• Step 2: Count papers for each citation:
  • citations = [10, 8, 5, 4, 3, 7, 2, 1]
  • papers = [0, 1, 1, 1, 1, 1, 0, 1, 2]
• Step 3: Find h-index:
  • Start with k = 8 and s = 2 (papers[8])
  • For k = 8, s = 2 + 0 = 2 (move to next)
  • For k = 7, s = 2 + 1 = 3 (move to next)
  • For k = 6, s = 3 + 0 = 3 (move to next)
  • For k = 5, s = 3 + 1 = 4 (move to next)
  • For k = 4, s = 4 + 1 = 5 (stop, since s >= k)
• Step 4: Return h = 4

Code

public class Solution {

  public int hIndex(int[] citations) {
    int n = citations.length;
    int[] papers = new int[n + 1];
    // Count papers for each citation number
    for (int c : citations) {
      papers[Math.min(n, c)]++;
    }
    // Find the h-index
    int k = n;
    for (int s = papers[n]; k > s; s += papers[k]) {
      k--;
    }
    return k;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.hIndex(new int[] { 4, 3, 0, 1, 5 })); // Output: 3
    System.out.println(sol.hIndex(new int[] { 10, 8, 5, 4, 3, 7, 2, 1 })); // Output: 4
    System.out.println(sol.hIndex(new int[] { 0, 1, 2, 3, 4 })); // Output: 2
  }
}

Complexity Analysis

• Time Complexity: Counting the citations takes , and finding the h-index also takes . Thus, the overall time complexity is .
• Space Complexity: The algorithm uses additional space for the papers array.

Pattern Transfer — COUNTING BUCKETS + SUFFIX ACCUMULATION

Pattern name: counting sort style histogram + scan from high h downward.

Why min(c, n) / bucket size n+1: h-index cannot exceed n (you only have n papers). Any citation count > n is indistinguishable from n for computing h.

Clearer loop form (equivalent to the compact for):

k = n
s = papers[n]           # papers with ≥ n citations (bucket n)
while k > s:
  k -= 1
  s += papers[k]        # now s = #papers with ≥ k citations
return k

Invariant: after updates, s is the number of papers with at least k citations; we shrink k until s ≥ k.

Step table for [10,8,5,4,3,7,2,1] (n=8)

After bucketing (cap at 8): walk k from 8 downward until s≥k; ends at h=4 (5 papers with ≥4 cites; only 4 with ≥5).

k	s (papers ≥ k)	k > s?
8	papers[8]=2	yes → k=7, s+=papers[7]
…	… continue …	…
4	5	no → return 4

Sort alternate: sort descending O(n log n) time, O(1) extra if in-place; scan for largest i with citations[i] ≥ i+1. Prefer counting when O(n) time / O(n) space is fine.

Complexity: fill buckets Θ(n) + scan ≤ n steps → Θ(n) time, Θ(n) space.

Edge hand-runs

• [0,0,0]: all mass in papers[0]; k shrinks to 0 → 0.
• [100]: papers[1] += 1 (capped); h=1.

Drill: Prove h ≤ n always from the definition.