  # LeetCode - Find the Prefix Common Array of Two Arrays

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays

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.
At i = 1: 1 and 3 are common in A and B, so C = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C = 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.
At i = 1: only 3 is common in A and B, so C = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C = 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.
``````

### Explanation

#### Brute Force

We need to return an array result of the same length such that result[i] is the number of elements that are common in both A and B. We can start by creating two hash maps map1 and m2 to store the indices of each element in A and B, respectively.

We then iterate over array A and count the number of elements that are common to both A and B up to that point. We do this by checking if the index of each element in A is less than or equal to i and the index of the same element in B is also less than or equal to i. We store the count in an array result and return it as the answer.

A C++ snippet of the above approach is as follows:

``````vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int n = A.size();
unordered_map<int, int> map1, map2;

for(int i = 0; i < n; i++) {
map1[A[i]] = i;
map2[B[i]] = i;
}

vector<int> result(n);

for(int i = 0; i < n; i++) {
int count = 0;

for(int j = 0; j <= i; j++) {
if(m1[A[j]] <= i && m2[A[j]] <= i) {
count++;
}
}

result[i] = count;
}

return result;
}``````

The time complexity of this solution is O(n^2), since we are using two nested for loops. The space complexity is O(n).

#### Efficient solution

To find the prefix common array, we can iterate over arrays A and B simultaneously and keep track of the frequency of each integer in both arrays using an array seen. For each element in A and B, we increment the corresponding element in seen and check if its frequency becomes 2. If the frequency becomes 2, it means that the element is present in both A and B at or before the current index i.

We update the corresponding element in the result array result by adding 1 if the frequency of the element in A or B becomes 2, otherwise we add 0.

Finally, we compute the prefix sum of the result array to get the prefix common array of A and B.

Let's check the algorithm to understand it clearly.

#### Algorithm

``````- set current = 0
n = A.size()

- set result(n)
seen(n + 1)

- loop for i = 0; i < n; i++
- seen[A[i]] = seen[A[i]] + 1
- if seen[A[i]] == 2
- current++
- if end

- seen[B[i]] = seen[B[i]] + 1
- if seen[B[i]] == 2
- current++
- if end

- result[i] = current
- for end

- return result
``````

The time complexity of this approach is O(n). The space complexity of this approach is O(n).

Let's check out our solutions in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int current = 0, n = A.size();
vector<int> result(n), seen(n + 1);

for (int i = 0; i < n; ++i) {
if (++seen[A[i]] == 2) {
current++;
}

if (++seen[B[i]] == 2) {
current++;
}

result[i] = current;
}
return result;
}
};``````

#### Golang solution

``````func findThePrefixCommonArray(A []int, B []int) []int {
current, n := 0, len(A)
result, seen := make([]int, n), make([]int, n + 1)

for i := 0; i < n; i++ {
seen[A[i]]++
if seen[A[i]] == 2 {
current++
}

seen[B[i]]++
if seen[B[i]] == 2 {
current++
}

result[i] = current
}

return result
}``````

#### JavaScript solution

``````var findThePrefixCommonArray = function(A, B) {
let current = 0, n = A.length;
let result = new Array(n), seen = new Array(n + 1).fill(0);

for (let i = 0; i < n; ++i) {
if (++seen[A[i]] == 2) {
current++;
}

if (++seen[B[i]] == 2) {
current++;
}

result[i] = current;
}

return result;
};``````

#### Dry Run

Let's dry-run our algorithm for a few examples to see how the solution works.

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

Step 1: int current = 0, n = A.size();
vector<int> result(n), seen(n + 1);

Step 2: loop for i = 0; i < n;
0 < 4
true

if ++seen[A[i]] == 2
A[i] = A
= 1

seen[A[i]] = seen[A]
= seen
= 0

++seen[A[i]] = 1

1 == 2
false

seen = [0, 1, 0, 0, 0]

if ++seen[B[i]] == 2
B[i] = B
= 3

seen[B[i]] = seen[B]
= seen
= 0

++seen[B[i]] = 1

1 == 2
false

seen = [0, 1, 0, 1, 0]

result[i] = current
result = 0
result = [0, 0, 0, 0]

i++
i = 1

Step 3: for i < n
1 < 4
true

if ++seen[A[i]] == 2
A[i] = A
= 3

seen[A[i]] = seen[A]
= seen
= 1

++seen[A[i]] = 2

2 == 2
true
current++
current = 1

seen = [0, 1, 0, 2, 0]

if ++seen[B[i]] == 2
B[i] = B
= 1

seen[B[i]] = seen[B]
= seen
= 1

++seen[B[i]] = 2

2 == 2
true

current++
current = 2

seen = [0, 2, 0, 2, 0]

result[i] = current
result = 2
result = [0, 2, 0, 0]

i++
i = 2

Step 4: for i < n
2 < 4
true

if ++seen[A[i]] == 2
A[i] = A
= 2

seen[A[i]] = seen[A]
= seen
= 0

++seen[A[i]] = 1

1 == 2
false

seen = [0, 2, 1, 2, 0]

if ++seen[B[i]] == 2
B[i] = B
= 2

seen[B[i]] = seen[B]
= seen
= 1

++seen[B[i]] = 2

2 == 2
true

current++
current = 3

seen = [0, 2, 2, 2, 0]

result[i] = current
result = 3
result = [0, 2, 3, 0]

i++
i = 3

Step 5: for i < n
3 < 4
true

if ++seen[A[i]] == 2
A[i] = A
= 4

seen[A[i]] = seen[A]
= seen
= 0

++seen[A[i]] = 1

1 == 2
false

seen = [0, 2, 2, 2, 1]

if ++seen[B[i]] == 2
B[i] = B
= 4

seen[B[i]] = seen[B]
= seen
= 1

++seen[B[i]] = 2

2 == 2
true

current++
current = 4

seen = [0, 2, 2, 2, 2]

result[i] = current
result = 4
result = [0, 2, 3, 4]

i++
i = 4

Step 6: for i < n
4 < 4
false

Step 7: return result

We return the result as [0, 2, 3, 4].
``````