2657. Find the Prefix Common Array of Two Arrays

Description

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

Solutions

Solution 1: Counting

We can use two arrays \(cnt1\) and \(cnt2\) to record the occurrence times of each element in arrays \(A\) and \(B\) respectively, and use an array \(ans\) to record the answer.

Traverse arrays \(A\) and \(B\), increment the occurrence times of \(A[i]\) in \(cnt1\), and increment the occurrence times of \(B[i]\) in \(cnt2\). Then enumerate \(j \in [1,n]\), calculate the minimum occurrence times of each element \(j\) in \(cnt1\) and \(cnt2\), and accumulate them into \(ans[i]\).

After the traversal, return the answer array \(ans\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of arrays \(A\) and \(B\).

Python3JavaC++GoTypeScript

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        cnt1 = Counter()
        cnt2 = Counter()
        for a, b in zip(A, B):
            cnt1[a] += 1
            cnt2[b] += 1
            t = sum(min(v, cnt2[x]) for x, v in cnt1.items())
            ans.append(t)
        return ans

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] ans = new int[n];
        int[] cnt1 = new int[n + 1];
        int[] cnt2 = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            ++cnt1[A[i]];
            ++cnt2[B[i]];
            for (int j = 1; j <= n; ++j) {
                ans[i] += Math.min(cnt1[j], cnt2[j]);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> ans(n);
        vector<int> cnt1(n + 1), cnt2(n + 1);
        for (int i = 0; i < n; ++i) {
            ++cnt1[A[i]];
            ++cnt2[B[i]];
            for (int j = 1; j <= n; ++j) {
                ans[i] += min(cnt1[j], cnt2[j]);
            }
        }
        return ans;
    }
};

func findThePrefixCommonArray(A []int, B []int) []int {
    n := len(A)
    cnt1 := make([]int, n+1)
    cnt2 := make([]int, n+1)
    ans := make([]int, n)
    for i, a := range A {
        b := B[i]
        cnt1[a]++
        cnt2[b]++
        for j := 1; j <= n; j++ {
            ans[i] += min(cnt1[j], cnt2[j])
        }
    }
    return ans
}

function findThePrefixCommonArray(A: number[], B: number[]): number[] {
    const n = A.length;
    const cnt1: number[] = Array(n + 1).fill(0);
    const cnt2: number[] = Array(n + 1).fill(0);
    const ans: number[] = Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        ++cnt1[A[i]];
        ++cnt2[B[i]];
        for (let j = 1; j <= n; ++j) {
            ans[i] += Math.min(cnt1[j], cnt2[j]);
        }
    }
    return ans;
}

Solution 2: Bit Operation (XOR Operation)

We can use an array \(vis\) of length \(n+1\) to record the occurrence situation of each element in arrays \(A\) and \(B\), the initial value of array \(vis\) is \(1\). In addition, we use a variable \(s\) to record the current number of common elements.

Next, we traverse arrays \(A\) and \(B\), update \(vis[A[i]] = vis[A[i]] \oplus 1\), and update \(vis[B[i]] = vis[B[i]] \oplus 1\), where \(\oplus\) represents XOR operation.

If at the current position, the element \(A[i]\) has appeared twice (i.e., it has appeared in both arrays \(A\) and \(B\)), then the value of \(vis[A[i]]\) will be \(1\), and we increment \(s\). Similarly, if the element \(B[i]\) has appeared twice, then the value of \(vis[B[i]]\) will be \(1\), and we increment \(s\). Then add the value of \(s\) to the answer array \(ans\).