// Algorithm / 演算法：counting-sort bucket. Cap each citation at n, drop into a bucket,
// then sweep h from n down to 0 accumulating "papers with ≥ h citations". The first
// h where that running count >= h is the h-index. O(n) time, O(n) space.

#include <stdlib.h>   // malloc, calloc, free / 動態記憶體配置函式
#include <string.h>   // (not strictly needed, kept for portability / 可移植性保留)

int hIndex(int* citations, int citationsSize) {
    int n = citationsSize;                       // n = 論文總數 / total number of papers

    // 配置長度 n+1 的桶子陣列，calloc 會把每格初始化為 0
    // Allocate a bucket array of length n+1; calloc zero-initializes every slot.
    int* bucket = (int*)calloc(n + 1, sizeof(int));

    // 第一輪：把每篇論文丟進對應桶子 / First pass: drop each paper into its bucket
    for (int i = 0; i < n; i++) {
        int c = citations[i];                    // 取出第 i 篇的引用數 / read i-th citation count
        // 引用數 > n 的論文一律塞進 bucket[n]，因為 h 不可能超過 n
        // Anything > n collapses into bucket[n], since h cannot exceed n.
        if (c >= n) {
            bucket[n]++;                         // 大於等於 n 的篇數 +1 / count of papers with ≥ n citations
        } else {
            bucket[c]++;                         // 否則丟進對應引用數的桶子 / otherwise, exact citation bucket
        }
    }

    // 第二輪：從 h = n 往下掃，count 累計「引用數 >= h 的論文數」
    // Second pass: sweep h from n down, accumulating papers with ≥ h citations.
    int count = 0;                               // 後綴累計 / running suffix count
    for (int h = n; h >= 0; h--) {
        count += bucket[h];                      // 加上恰好 h 次引用的論文 / add papers with exactly h citations
        // 第一個滿足 count >= h 的 h 就是答案（h 從大到小掃，自然找到最大值）
        // First h with count >= h is the answer (we scan top-down, so it's the maximum).
        if (count >= h) {
            free(bucket);                        // 釋放桶子 / free the heap allocation
            return h;                            // 回傳答案 / return result
        }
    }

    // 理論上 h = 0 一定成立，迴圈內就會回傳；這行只是給編譯器看
    // h = 0 always satisfies count >= 0, so the loop always returns; this is just a fallback.
    free(bucket);
    return 0;
}