H-Index — DSA · Engineering Playbook

Problem#

Given an array citations where citations[i] is the citation count of the i-th paper, return the researcher’s h-index: the largest h such that at least h papers each have at least h citations.

Examples#

citations = [3,0,6,1,5] → 3
citations = [1,3,1] → 1
citations = [0,0,0,0] → 0

Constraints#

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

Approach#

Bucket counts at index min(c, n) — any citation count above n is capped because the h-index can’t exceed n. Then sweep from the highest bucket down, accumulating the count of papers with at least h citations; the first h where that running count is >= h is the answer.

Solution#

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        vector<int> bucket(n + 1, 0);
        for (int c : citations) bucket[min(c, n)]++;
        int count = 0;
        for (int h = n; h >= 0; --h) {
            count += bucket[h];
            if (count >= h) return h;
        }
        return 0;
    }
};

func hIndex(citations []int) int {
    n := len(citations)
    bucket := make([]int, n+1)
    for _, c := range citations {
        if c > n {
            c = n
        }
        bucket[c]++
    }
    count := 0
    for h := n; h >= 0; h-- {
        count += bucket[h]
        if count >= h {
            return h
        }
    }
    return 0
}

from typing import List

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        bucket = [0] * (n + 1)
        for c in citations:
            bucket[min(c, n)] += 1
        count = 0
        for h in range(n, -1, -1):
            count += bucket[h]
            if count >= h:
                return h
        return 0

function hIndex(citations) {
    const n = citations.length;
    const bucket = new Array(n + 1).fill(0);
    for (const c of citations) bucket[Math.min(c, n)]++;
    let count = 0;
    for (let h = n; h >= 0; h--) {
        count += bucket[h];
        if (count >= h) return h;
    }
    return 0;
}

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] bucket = new int[n + 1];
        for (int c : citations) bucket[Math.min(c, n)]++;
        int count = 0;
        for (int h = n; h >= 0; h--) {
            count += bucket[h];
            if (count >= h) return h;
        }
        return 0;
    }
}

function hIndex(citations: number[]): number {
    const n = citations.length;
    const bucket: number[] = new Array(n + 1).fill(0);
    for (const c of citations) bucket[Math.min(c, n)]++;
    let count = 0;
    for (let h = n; h >= 0; h--) {
        count += bucket[h];
        if (count >= h) return h;
    }
    return 0;
}

Editorial#

Bucket counting avoids the O(n log n) sort and exploits the fact that the answer is bounded by n. Walking from the top down tracks “papers with at least h citations” as a running sum.

Complexity#

Time: O(n).
Space: O(n).

Concept revision#

Find Target Indices After Sorting Array

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#