# 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] = 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.
```

### 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[0]
= 1
seen[A[i]] = seen[A[0]]
= seen[1]
= 0
++seen[A[i]] = 1
1 == 2
false
seen = [0, 1, 0, 0, 0]
if ++seen[B[i]] == 2
B[i] = B[0]
= 3
seen[B[i]] = seen[B[0]]
= seen[3]
= 0
++seen[B[i]] = 1
1 == 2
false
seen = [0, 1, 0, 1, 0]
result[i] = current
result[0] = 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[1]
= 3
seen[A[i]] = seen[A[1]]
= seen[3]
= 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]
= 1
seen[B[i]] = seen[B[0]]
= seen[1]
= 1
++seen[B[i]] = 2
2 == 2
true
current++
current = 2
seen = [0, 2, 0, 2, 0]
result[i] = current
result[1] = 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]
= 2
seen[A[i]] = seen[A[2]]
= seen[2]
= 0
++seen[A[i]] = 1
1 == 2
false
seen = [0, 2, 1, 2, 0]
if ++seen[B[i]] == 2
B[i] = B[2]
= 2
seen[B[i]] = seen[B[2]]
= seen[2]
= 1
++seen[B[i]] = 2
2 == 2
true
current++
current = 3
seen = [0, 2, 2, 2, 0]
result[i] = current
result[2] = 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[3]
= 4
seen[A[i]] = seen[A[2]]
= seen[4]
= 0
++seen[A[i]] = 1
1 == 2
false
seen = [0, 2, 2, 2, 1]
if ++seen[B[i]] == 2
B[i] = B[3]
= 4
seen[B[i]] = seen[B[3]]
= seen[4]
= 1
++seen[B[i]] = 2
2 == 2
true
current++
current = 4
seen = [0, 2, 2, 2, 2]
result[i] = current
result[3] = 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].
```