// 演算法 / Algorithm:
// 三趟線性掃描 / three linear passes. Pass 1 copies all elements < pivot in order,
// pass 2 copies all elements == pivot, pass 3 copies all elements > pivot.
// 各組天然保持原相對順序 / each group keeps its original relative order automatically.

/**
 * LeetCode 的簽名：回傳新陣列，並透過 returnSize 回傳長度。
 * LeetCode signature: return a new array and report its length via returnSize.
 */
int* pivotArray(int* nums, int numsSize, int pivot, int* returnSize) {
    // 配置一塊和輸入一樣大的記憶體當作答案陣列。
    // Allocate an answer array the same size as the input.
    // malloc 回傳指向該記憶體的指標 / malloc returns a pointer to that memory.
    int* res = (int*)malloc(sizeof(int) * numsSize);

    // k 是「下一個要寫入的位置」/ k is the next write slot in res.
    int k = 0;

    // 第一趟：把所有小於 pivot 的元素，依原順序填入。
    // Pass 1: copy every element strictly less than pivot, in order.
    for (int i = 0; i < numsSize; i++) {       // i 從頭掃到尾 / scan i from start to end
        if (nums[i] < pivot) {                 // 只挑「小於」的 / pick only the smaller ones
            res[k] = nums[i];                  // 寫入答案 / write into res at slot k
            k++;                               // 寫入位置前移一格 / advance the write slot
        }
    }

    // 第二趟：把所有等於 pivot 的元素填入。
    // Pass 2: copy every element equal to pivot.
    // 它們都等於 pivot，順序無所謂 / they are all equal to pivot, so order does not matter.
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == pivot) {                // 只挑「等於」的 / pick only the equal ones
            res[k] = nums[i];                  // 寫入（其值就是 pivot）/ write it (equals pivot)
            k++;                               // 前移寫入位置 / advance write slot
        }
    }

    // 第三趟：把所有大於 pivot 的元素，依原順序填入。
    // Pass 3: copy every element strictly greater than pivot, in order.
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > pivot) {                 // 只挑「大於」的 / pick only the larger ones
            res[k] = nums[i];                  // 寫入答案 / write into res
            k++;                               // 前移寫入位置 / advance write slot
        }
    }

    // 告訴呼叫者答案陣列的長度（和輸入一樣長）。
    // Tell the caller the length of the answer array (same as input).
    *returnSize = numsSize;                    // *returnSize 是解參考並賦值 / dereference and assign

    return res;                                // 回傳答案陣列的指標 / return the pointer to res
}