The problem. citations[i] is how many times a researcher's i-th paper has been cited. Their h-index is the largest h such that they have at least h papers with at least h citations each. Return it.
citations = [3, 0, 6, 1, 5] -> 3 (3 papers with at least 3 citations)
citations = [1, 3, 1] -> 1
citations = [10, 8, 9] -> 3 (h can't exceed the number of papers)Sort the citations from most to least cited. Then "h papers with at least h citations" means: the first h papers all have at least h — and since they're sorted, only the weakest of them, the h-th, needs checking. So walk down the sorted list while paper number h + 1 still has at least h + 1 citations. Where that fails, h is the answer.
function hIndex(citations) { for (let h = citations.length; h > 0; h--) { const enough = citations.filter((c) => c >= h).length; // papers with at least h citations if (enough >= h) return h; } return 0;}Time O(n²), space O(1). Up to n candidate values of h, each counted over all n papers.
Sorted most cited first, h grows while paper #(h+1) still has at least h+1 citations.
function hIndex(citations) { const c = [...citations].sort((a, b) => b - a); // most cited first let h = 0; while (h < c.length && c[h] >= h + 1) h++; // the (h+1)-th best paper has at least h+1 citations return h;}Time O(n log n), space O(n) for the sorted copy.
h can never exceed n, so any paper with more than n citations can be counted as n. Count how many papers have each number of citations from 0 to n, then walk down from n adding up papers until the total reaches the current value.
function hIndex(citations) { const n = citations.length; const count = new Array(n + 1).fill(0); for (const c of citations) count[Math.min(c, n)]++; // more than n citations counts as n let papers = 0; for (let h = n; h > 0; h--) { papers += count[h]; // papers with at least h citations if (papers >= h) return h; } return 0;}Time O(n), space O(n). A counting sort in disguise — the key insight is capping at n.
[3, 3, 3] gives 3.