2657. Find the Prefix Common Array of Two Arrays

題目 / Problem

中文： 給定兩個長度為 n 的 0-indexed 整數排列 A 和 B（也就是說，兩個陣列各自都恰好包含 1 到 n 的每個整數一次）。

定義 前綴共同陣列（prefix common array） C：C[i] 等於「同時出現在 A[0..i] 和 B[0..i] 中的數字個數」。

請回傳 C。

English: You are given two 0-indexed integer permutations A and B of length n (each array contains every integer from 1 to n exactly once).

Define the prefix common array C: C[i] is the count of numbers that appear in both A[0..i] and B[0..i].

Return C.

Constraints / 限制： - 1 <= n <= 50 - 1 <= A[i], B[i] <= n - A and B are both permutations of 1..n.

Worked example / 範例：

Input:  A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]

• i=0: A 的前綴 = {1}, B 的前綴 = {3}，沒有共同 → C[0]=0
• i=1: A 的前綴 = {1,3}, B 的前綴 = {3,1}，共同 = {1,3} → C[1]=2
• i=2: 加入 2，共同 = {1,2,3} → C[2]=3
• i=3: 加入 4，共同 = {1,2,3,4} → C[3]=4

名詞解釋 / Glossary

• 排列 / Permutation：長度 n 的陣列，恰好包含 1 到 n 每個整數一次，沒有重複。A permutation of length n is an array containing each integer from 1 to n exactly once.
• 前綴 / Prefix：陣列從第 0 個元素到某個索引 i 為止的子陣列，記作 A[0..i]。The subarray from index 0 up to and including index i.
• 頻率陣列 / Frequency array (counting array)：一個整數陣列 freq，freq[x] 記錄數字 x 到目前為止出現過幾次。常用於數字範圍小且已知時，代替雜湊表，速度更快。An integer array where freq[x] stores how many times the value x has been seen so far — a fast alternative to a hash map when the value range is small and bounded.
• 計數技巧（出現兩次）/ "Seen twice" trick：把 A 和 B 的數字都丟進同一個頻率陣列；因為兩者各自都是排列（自己內部不重複），所以同一個數字頻率達到 2 就代表「在 A 和 B 都出現過」。Drop both arrays' numbers into one shared counter; since each array has no internal duplicates, a count of 2 for some value x means x appeared in both A's prefix and B's prefix.
• calloc vs malloc（C 語言）：兩者都從堆積（heap）分配記憶體。malloc 不初始化內容（記憶體是垃圾值），calloc 會把所有 bytes 清成 0。本題我們需要頻率陣列從 0 開始，所以用 calloc。Both allocate heap memory; malloc leaves it uninitialized (garbage), while calloc zeroes it — perfect for a counter that must start at 0.
• vector<int>（C++）：標準函式庫提供的動態陣列，會自動管理大小和記憶體。vector<int>(n, 0) 建立長度 n、全部初始化為 0 的向量。STL dynamic array; vector<int>(n, 0) constructs one of length n filled with zeros.

思路

最直覺的「暴力解」是：對每個 i，把 A[0..i] 和 B[0..i] 都掃一遍，數出共同元素的數量；這需要兩層迴圈再加上一層比對，複雜度大約是 O(n³)，雖然 n ≤ 50 跑得動，但不夠漂亮。觀察題目給的關鍵條件：A 和 B 各自都是 1 到 n 的排列，所以「在 A 的前綴裡」這件事最多發生一次，「在 B 的前綴裡」也最多發生一次。我們維護一個共用的頻率表 freq：每往前走一步，把 A[i] 和 B[i] 各加進去；當某個數字的 freq 從 1 變成 2，就代表它「已經兩邊都出現過」，把答案 common 加一。最後 C[i] = common。因為每個數字在這個迴圈裡最多被計入一次（從 1 變 2 只會發生一次），這個演算法是正確的，而且只需要一次線性掃描。

The naive approach loops over every prefix, scans both A[0..i] and B[0..i], and counts overlaps — that's roughly O(n³) and wasteful. The key insight comes from the constraint that both arrays are permutations of 1..n, so any value appears at most once in A and at most once in B. We keep a single shared counter array freq: as we walk forward, we increment freq[A[i]] and freq[B[i]]. The moment any cell ticks from 1 to 2, that value must have appeared in both prefixes — so we bump a running common counter. Because each value can only make that 1→2 transition once, we never double-count, and the algorithm runs in a single linear pass.

逐步走查 / Walkthrough

以 A = [1,3,2,4], B = [3,1,2,4] 為例，追蹤 freq[1..4] 和 common：

最終結果 / Final result: C = [0, 2, 3, 4]，與題目期望輸出一致。

注意 i=2 那一步：A[2]=B[2]=2，所以同一個元素 freq[2] 在同一輪內被 +1 兩次，順利從 0 → 1 → 2，剛好觸發一次 common++。這正是「同一個迴圈內處理兩次加一、各自獨立檢查」的關鍵。

Note step i=2: since A[2] == B[2] == 2, the same cell freq[2] is incremented twice within one iteration, going 0 → 1 → 2 and triggering exactly one common++. That's why we check the 1→2 transition after each individual increment, not after both.

Solution — C

/*
 * 演算法 / 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)
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 與 C 版本相同：用一個 vector<int> freq 當作共用頻率表，
 * 每加入 A[i]、B[i] 後檢查是否從 1 變 2，若是就把 common 加一。O(n) 時間。
 * Same idea as the C version, using STL vector. Each 1->2 transition adds one to common.
 */

#include <vector>     // 提供 std::vector / Provides std::vector
using namespace std;  // 省略 std:: 前綴（教學用，正式專案通常避免）/ drop std:: prefix for readability

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();                           // n 是陣列長度 / length of A (and B)

        // vector<int>(n+1, 0) 建立長度 n+1、全為 0 的向量；
        // 因為題目值的範圍是 1..n，我們以值本身當索引，所以多開一格。
        // Counter indexed by value; values are 1..n, so size n+1.
        vector<int> freq(n + 1, 0);

        vector<int> result(n);                      // 結果向量，預設都是 0；我們會逐一覆寫 / result vector, will be overwritten
        int common = 0;                             // 已知兩邊都出現過的數字個數 / running count

        for (int i = 0; i < n; i++) {               // range-for 也可以，但用索引比較清楚 / index loop keeps things explicit
            // ++freq[A[i]] 是「先加一，再取值」(前置遞增) / pre-increment: add 1 first, then read the new value
            if (++freq[A[i]] == 2) common++;        // 若加完正好等於 2，代表 A、B 都出現過 / 1->2 means seen in both prefixes
            if (++freq[B[i]] == 2) common++;        // 對 B[i] 同樣處理 / same check for B[i]

            result[i] = common;                     // 寫入答案 / store answer
        }

        return result;                              // C++ 回傳 vector，記憶體由 STL 管理 / STL handles memory, just return by value
    }
};

複雜度 / Complexity

• Time: O(n) — 我們對輸入做一次線性掃描，每一步只做常數次的陣列存取與比較，所以總時間和 n（陣列長度）成正比。We do a single pass over the input; each iteration is O(1) work (array indexing + a comparison), so total time scales linearly with n.
• Space: O(n) — 額外使用了長度 n+1 的頻率陣列；輸出陣列 result 本身長度也是 n，但通常不算進額外空間。若不算輸出，輔助空間是 O(n)。We allocate a counter of size n+1; the output array is also size n but is usually not counted as auxiliary space. Auxiliary space is O(n).

Pitfalls & Edge Cases

• 同一輪內 A[i] == B[i] / Same value at both positions in one step：例如 A[2]=B[2]=2 時，freq[2] 會在同一個迴圈內從 0 → 1 → 2。要在「每次 ++ 之後」都檢查一次 == 2，不能合併成一次檢查，否則會漏算或多算。Check the == 2 condition after each increment, not after both — otherwise you'll miscount when the same value lives at the same index in both arrays.
• 只在 freq 從 1 變 2 時計數 / Only the 1→2 transition counts：因為 A、B 各自是排列，同一個數字在 A 裡最多出現一次，在 B 裡也最多一次，所以 freq 最多會到 2。若寫成 if (freq[A[i]] >= 2) 在這題雖然不會出錯（因為不會超過 2），但邏輯上 == 2 更精準、也更能表達「剛好兩邊都出現」的瞬間。Use == 2 exactly — values can never exceed 2 here because of the permutation constraint, but using == makes intent clear.
• 頻率陣列大小 / Counter array size：值的範圍是 1..n，所以要開 n+1 格（索引 0 不用，但保留它讓索引和值對齊）。If you allocate only n slots and try freq[n], that's an out-of-bounds write — classic off-by-one.
• C 版本記憶體管理 / Memory management in C：calloc 出來的 freq 必須在 return 前 free，否則洩漏。result 則交給 LeetCode 的測試框架釋放，不要自己 free。Free freq before returning; do not free result — LeetCode owns it after you return.
• returnSize 必填 / returnSize must be set：LeetCode 的 C 介面用 *returnSize 取得回傳陣列長度。忘了設定會導致讀到垃圾值。LeetCode's C harness reads *returnSize to know the array length — forget it and the judge sees garbage.