// 演算法 / Algorithm:
// 1) 掃一遍找出 min 與 max。 / Scan once to find min and max.
// 2) 用布林陣列 seen[] 標記每個出現過的值（值域小，1..100）。 / Mark presence in seen[].
// 3) 從 min 到 max 逐一檢查，未標記者即為缺失，依序收集（天生排序）。 / Collect unmarked = sorted missing.

/**
 * 注意 / Note: 回傳的陣列必須用 malloc 動態配置，
 * 並把長度寫進 *returnSize。 / Result must be heap-allocated; write length to *returnSize.
 */
int* findMissing(int* nums, int numsSize, int* returnSize) {
    // seen[v] 表示值 v 是否出現過；索引 0..100，故大小 101。
    // seen[v] tells whether value v appeared; indices 0..100, so size 101.
    // 用 {0} 把整個陣列初始化為 0（false）。/ {0} zero-initializes the whole array (all false).
    int seen[101] = {0};

    // 先用第一個元素當作 min 與 max 的初始值。/ Seed min & max with the first element.
    int minVal = nums[0];
    int maxVal = nums[0];

    // 走一遍陣列：更新 min/max，並標記存在。/ One pass: update min/max and mark presence.
    for (int i = 0; i < numsSize; i++) {
        int v = nums[i];                  // 取出目前的值 / current value
        if (v < minVal) minVal = v;       // 更小就更新 min / shrink min
        if (v > maxVal) maxVal = v;       // 更大就更新 max / grow max
        seen[v] = 1;                      // 標記 v 存在（1 = true）/ mark v as present
    }

    // 範圍內最多可能缺 (maxVal - minVal + 1) 個數，配置這麼大足夠。
    // At most (maxVal - minVal + 1) values in range; allocate that many to be safe.
    int capacity = maxVal - minVal + 1;
    // malloc 向系統要記憶體；sizeof(int) 是一個 int 的位元組數。
    // malloc requests memory; sizeof(int) is the byte size of one int.
    int* result = (int*)malloc(sizeof(int) * capacity);

    int k = 0;  // k 是下一個寫入位置，也等於已找到的缺失數量 / k = next write slot = count so far

    // 從 min 到 max 逐一檢查（含兩端）。/ Sweep every value in [min, max], inclusive.
    for (int v = minVal; v <= maxVal; v++) {
        // seen[v] 為 0（false）代表 v 沒出現，就是缺失的。
        // seen[v] == 0 means v never appeared, i.e. it is missing.
        if (seen[v] == 0) {
            result[k] = v;  // 把缺失值寫進結果陣列 / store the missing value
            k++;            // 位置往後移一格 / advance write slot
        }
    }

    *returnSize = k;  // 透過指標回傳結果長度給呼叫者 / report length via the out-pointer
    return result;    // 回傳動態配置的結果陣列 / return the heap-allocated array
}