H-Index Algorithm

The H-Index measures a researcher's impact. It's the largest number h such that the researcher has at least h papers with h or more citations each.

Simple definition, tricky to compute efficiently.

The Problem

Given citations = [3, 0, 6, 1, 5], return the h-index.

Output: 3
There are 3 papers with at least 3 citations each (papers with 3, 6, and 5 citations). The remaining papers have fewer than 3 citations. So h = 3.

The Sorting Approach

Sort descending. Walk through the sorted array. The h-index is the last position where citations[i] >= i + 1.

function hIndex(citations) {
  citations.sort((a, b) => b - a);

  let h = 0;
  for (let i = 0; i < citations.length; i++) {
    if (citations[i] >= i + 1) {
      h = i + 1;
    } else {
      break;
    }
  }

  return h;
}

console.log(hIndex([3, 0, 6, 1, 5])); // 3
console.log(hIndex([1, 3, 1]));        // 1

Why This Works

After sorting descending: [6, 5, 3, 1, 0].

• Index 0: 6 >= 1 → at least 1 paper with 1+ citations. h = 1.
• Index 1: 5 >= 2 → at least 2 papers with 2+ citations. h = 2.
• Index 2: 3 >= 3 → at least 3 papers with 3+ citations. h = 3.
• Index 3: 1 < 4 → stop.

Complexity

• Time: O(n log n) for sorting.
• Space: O(1) if sorting in place.

The O(n) Approach

You can avoid sorting with a counting trick. Since h can't be larger than n (the number of papers), create a count array of size n + 1.

function hIndexLinear(citations) {
  const n = citations.length;
  const counts = new Array(n + 1).fill(0);

  for (const c of citations) {
    counts[Math.min(c, n)]++;
  }

  let total = 0;
  for (let i = n; i >= 0; i--) {
    total += counts[i];
    if (total >= i) return i;
  }

  return 0;
}

console.log(hIndexLinear([3, 0, 6, 1, 5])); // 3

• Time: O(n).
• Space: O(n) for the count array.

The Trade-off

The sorting approach is simpler to understand and implement. The counting approach is faster but uses extra memory and is harder to reason about. For interview settings, I'd start with sorting and mention the O(n) optimization.