/*
 * Algorithm: two linear sweeps over nums.
 * 演算法：對 nums 進行兩次線性掃描。
 * Pass 1 fills answer[i] with the product of everything to the LEFT of i.
 * Pass 2 multiplies in the product of everything to the RIGHT of i, using one scalar.
 * 第一次掃描把 i 左邊的乘積放入 answer[i]，第二次掃描再乘上 i 右邊的乘積。
 * Result: O(n) time, O(1) extra space (excluding the returned output array).
 */

/* LeetCode's C signature returns a heap-allocated int* and writes the length via a pointer. */
/* LeetCode 的 C 介面回傳一個動態配置的 int*，並透過指標把長度寫回呼叫端。 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    /* Tell the caller the output length equals the input length. */
    /* 告訴呼叫端輸出長度等於輸入長度。 */
    *returnSize = numsSize;

    /* malloc allocates numsSize ints on the heap; LeetCode frees this for us. */
    /* malloc 在堆積上配置 numsSize 個 int 的空間；LeetCode 會自行釋放。 */
    int* answer = (int*)malloc(sizeof(int) * numsSize);

    /* Pass 1: build prefix (left-side) products into answer[]. */
    /* 第一次掃描：把每個位置左邊的乘積寫入 answer[]。 */
    int left = 1;                         /* left = product of nums[0..i-1] / 目前 i 左邊累積乘積 */
    for (int i = 0; i < numsSize; i++) {
        answer[i] = left;                 /* write BEFORE updating, so nums[i] itself is excluded / 先寫入再更新，排除自己 */
        left *= nums[i];                  /* fold nums[i] into the running left product / 把 nums[i] 併入累積乘積 */
    }

    /* Pass 2: walk right-to-left, multiplying in suffix (right-side) products. */
    /* 第二次掃描：從右往左，把右邊乘積乘進 answer[]。 */
    int right = 1;                        /* right = product of nums[i+1..n-1] / 目前 i 右邊累積乘積 */
    for (int i = numsSize - 1; i >= 0; i--) {
        answer[i] *= right;               /* combine left product (already in answer[i]) with right product / 結合左、右乘積 */
        right *= nums[i];                 /* fold nums[i] into the running right product / 把 nums[i] 併入右側累積乘積 */
    }

    /* answer now holds the final products; return the heap pointer. */
    /* answer 已經是最終答案；回傳這個堆積指標。 */
    return answer;
}