H-Index

Problem

Given an array citations where citations[i] is the number of citations a researcher's i-th paper received, return the researcher's h-index: the maximum value h such that h papers each have at least h citations.

Constraints

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

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def hIndex(self, citations):
        citations.sort(reverse=True)
        h = 0
        for i, c in enumerate(citations):
            if c >= i + 1:
                h = i + 1
            else:
                break
        return h

Java

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)]++; // cap counts at n
        int sum = 0;
        for (int i = n; i >= 0; i--) {
            sum += bucket[i];        // papers with ≥ i citations
            if (sum >= i) return i;
        }
        return 0;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.