Problem #274: H-Index

Intuition & Strategy Breakdown

Sort citations array in descending order (or use bucket sort). Find max H such that citations[H-1] >= H.

Python Solution

class Solution:
    def hIndex(self, citations: list[int]) -> int:
        n = len(citations)
        paper_counts = [0] * (n + 1)
        for c in citations:
            paper_counts[min(n, c)] += 1
        h = n
        papers = paper_counts[n]
        while papers < h:
            h -= 1
            papers += paper_counts[h]
        return h

Java Solution

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] counts = new int[n + 1];
        for (int c : citations) {
            counts[Math.min(n, c)]++;
        }
        int k = n;
        for (int s = counts[n]; k > s; s += counts[k]) {
            k--;
        }
        return k;
    }
}