/*
 * 演算法 / Algorithm:
 * 維護一個共用頻率陣列 freq[1..n]，逐步把 A[i] 與 B[i] 加進去。
 * 因為 A、B 都是 1..n 的排列（自己內部不重複），所以某格從 1 變 2 就代表
 * "該數字同時出現在 A 和 B 的前綴裡"，把 common 加一即可。O(n) 時間。
 * Walk both arrays in lockstep, bumping a shared frequency table; any cell
 * going 1->2 means the value now exists in BOTH prefixes -> common++.
 */

#include <stdlib.h>  // 提供 calloc / malloc / free / Provides calloc, malloc, free

int* findThePrefixCommonArray(int* A, int aSize, int* B, int bSize, int* returnSize) {
    int n = aSize;                                  // n 是陣列長度 / array length (aSize == bSize)

    // calloc(n+1, ...) 配置 n+1 個 int 並全部初始化為 0；
    // 我們用索引 1..n（值的範圍），所以多開一格避免 off-by-one。
    // calloc allocates and zero-initializes; we use indices 1..n, so allocate n+1.
    int* freq = (int*)calloc(n + 1, sizeof(int));

    // 結果陣列長度 n；malloc 不歸零但我們每格都會寫入，所以沒關係。
    // Result array of length n; malloc is fine since every cell is written below.
    int* result = (int*)malloc(n * sizeof(int));

    int common = 0;                                 // 累積到目前為止「兩邊都出現過」的數字個數 / running count of values seen in both prefixes

    for (int i = 0; i < n; i++) {                   // 一次線性掃描 / single linear pass
        freq[A[i]]++;                               // A[i] 計數 +1 / bump counter for A[i]
        if (freq[A[i]] == 2) common++;              // 若剛好從 1 變 2，代表兩邊都出現了 / 1->2 means value is now in both prefixes

        freq[B[i]]++;                               // B[i] 計數 +1 / bump counter for B[i]
        if (freq[B[i]] == 2) common++;              // 同上：1->2 才算共同 / only the 1->2 transition counts

        result[i] = common;                         // 寫入第 i 個答案 / record answer for index i
    }

    free(freq);                                     // 釋放暫存的頻率陣列 / free the temporary counter array
    *returnSize = n;                                // 透過指標回傳結果長度（LeetCode C harness 規定）/ LeetCode's C API requires writing the length here
    return result;                                  // 回傳 heap 上的陣列指標（LeetCode 會幫忙 free）/ return heap pointer (LeetCode frees it)
}