# Find the Prefix Common Array of Two Arrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/find-the-prefix-common-array-of-two-arrays
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
---
## Problem
You are given two **0-indexed** integerpermutations `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.`

# Approaches
## Brute Force using Sets for Each Prefix
This approach directly follows the problem definition. We iterate through each possible prefix length, from 1 to `n`. For each length `i+1`, we consider the subarrays `A[0...i]` and `B[0...i]`. We convert these two subarrays into sets to easily find their common elements. The size of the intersection of these two sets gives us the value for `C[i]`.
**Time:** O(n^2). The outer loop runs `n` times. Inside the loop, we build two sets of size `i+1` and then iterate through one to find the intersection. This takes O(i) time. The total time is the sum of O(i) for `i` from 0 to `n-1`, which is O(n^2). · **Space:** O(n). At each step `i`, we create two sets that can grow up to size `n`. The space required is proportional to the largest prefix, which is `n`.
**Pros:** Simple to understand and implement, as it directly translates the problem statement.
**Cons:** Inefficient due to redundant computations. For each `i`, it re-scans and re-processes all elements in the prefixes up to `i`.
### Explanation
This method is straightforward but computationally expensive. For every index `i`, it constructs the prefixes of `A` and `B` from scratch, converts them to sets, and then computes the intersection size. This leads to a quadratic time complexity because the work done at each step `i` is proportional to `i`, and this is repeated for all `n` steps.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] C = new int[n];

        for (int i = 0; i < n; i++) {
            Set<Integer> setA = new HashSet<>();
            for (int j = 0; j <= i; j++) {
                setA.add(A[j]);
            }

            Set<Integer> setB = new HashSet<>();
            for (int j = 0; j <= i; j++) {
                setB.add(B[j]);
            }

            int commonCount = 0;
            for (int num : setA) {
                if (setB.contains(num)) {
                    commonCount++;
                }
            }
            C[i] = commonCount;
        }
        return C;
    }
}
```
### Algorithm
- Initialize an integer array `C` of size `n`.
- Loop with an index `i` from `0` to `n-1`.
- Inside the loop, create two hash sets, `setA` and `setB`.
- Populate `setA` with elements from `A[0...i]`.
- Populate `setB` with elements from `B[0...i]`.
- Initialize a counter `commonCount` to 0.
- Iterate through the elements of `setA`. For each element, check if it is present in `setB`.
- If an element is found in both sets, increment `commonCount`.
- After checking all elements, assign `C[i] = commonCount`.
- After the loop finishes, return the array `C`.

## Incremental Counting with Two Hash Sets
This approach improves upon the brute-force method by avoiding re-computation. Instead of creating new sets for each prefix, we maintain two running sets, one for the elements seen so far in `A` and one for `B`. As we iterate from `i = 0` to `n-1`, we add the new elements `A[i]` and `B[i]` to their respective sets and incrementally update the count of common elements.
**Time:** O(n). We iterate through the arrays once. Inside the loop, hash set operations (add, contains) take, on average, O(1) time. · **Space:** O(n). We use two hash sets that can store up to `n` elements each in the worst case.
**Pros:** Much more efficient than the brute-force approach.; Solves the problem in a single pass with O(n) time complexity.
**Cons:** Uses two separate hash sets, which can be slightly less space-efficient than a single frequency array.
### Explanation
By maintaining running sets, we can determine the new common count in constant time at each step. When we consider `A[i]` and `B[i]`, the count of common elements only increases if `A[i]` was already seen in `B`'s prefix, or if `B[i]` was already seen in `A`'s prefix, or if `A[i]` and `B[i]` are the same. This avoids the O(i) work of recalculating the intersection at each step, leading to a linear time solution.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] C = new int[n];
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setB = new HashSet<>();
        int commonCount = 0;

        for (int i = 0; i < n; i++) {
            int valA = A[i];
            int valB = B[i];

            setA.add(valA);
            setB.add(valB);

            if (valA == valB) {
                commonCount++;
            } else {
                if (setB.contains(valA)) {
                    commonCount++;
                }
                if (setA.contains(valB)) {
                    commonCount++;
                }
            }
            
            C[i] = commonCount;
        }
        return C;
    }
}
```
*Note: A slight logic correction is made in the code to add elements to sets before checking to handle the `valA == valB` case more cleanly within the `else` block logic.* A better way is presented in the description above.
### Algorithm
- Initialize an integer array `C` of size `n`.
- Initialize two empty hash sets, `setA` and `setB`.
- Initialize a counter `commonCount` to 0.
- Loop with an index `i` from `0` to `n-1`.
- Let `valA = A[i]` and `valB = B[i]`.
- If `valA` is equal to `valB`, it means a new number has appeared in both prefixes simultaneously. We increment `commonCount`.
- If `valA` is not equal to `valB`:
    - Check if `valA` is already present in `setB`. If so, adding `valA` to `setA` makes it a new common element, so we increment `commonCount`.
    - Check if `valB` is already present in `setA`. If so, adding `valB` to `setB` makes it a new common element, so we increment `commonCount`.
- Add `valA` to `setA` and `valB` to `setB`.
- Assign `C[i] = commonCount`.
- After the loop, return `C`.

## Single Pass with Frequency Array
This is the most optimized approach. It builds upon the incremental idea but uses a single data structure, a frequency array, to track the occurrences of each number across both prefixes. Since the input arrays are permutations of numbers from 1 to `n`, we can use a simple array of size `n+1` for this purpose.
**Time:** O(n). We iterate through the arrays once, and all operations inside the loop (array access, increment) are O(1). · **Space:** O(n). We use a frequency array of size `n+1` and the result array `C` of size `n`.
**Pros:** Highly efficient in both time and space.; Elegant and simple implementation that leverages the problem constraints (permutation of 1 to `n`).; Typically faster in practice than hash-based solutions due to better memory locality and no hashing overhead.
**Cons:** This specific implementation relies on the numbers being a permutation of 1 to `n`. If the numbers were arbitrary or from a large range, a hash map would be needed instead of an array, which would have similar performance to the two-set approach.
### Explanation
A number is common to both prefixes up to index `i` if it has been seen once in `A`'s prefix and once in `B`'s prefix. We can track this using a single frequency array. For each number `x`, `freq[x]` will store the total number of times `x` has appeared in `A[0...i]` and `B[0...i]` combined. When `freq[x]` becomes 2, it signifies that `x` has appeared in both prefixes for the first time, so we increment our common count. This is the most efficient method as it uses direct array indexing which is faster than hashing.

```java
class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] C = new int[n];
        int[] freq = new int[n + 1];
        int commonCount = 0;

        for (int i = 0; i < n; i++) {
            // Process element from A
            freq[A[i]]++;
            if (freq[A[i]] == 2) {
                commonCount++;
            }

            // Process element from B
            // This handles the A[i] == B[i] case correctly. 
            // If A[i] == B[i], freq[A[i]] will be incremented to 1, then to 2 in the same iteration.
            freq[B[i]]++;
            if (freq[B[i]] == 2) {
                commonCount++;
            }
            
            C[i] = commonCount;
        }
        return C;
    }
}
```
### Algorithm
- Initialize an integer array `C` of size `n`.
- Initialize a frequency array `freq` of size `n+1` with all values as 0.
- Initialize a counter `commonCount` to 0.
- Loop with an index `i` from `0` to `n-1`.
- For the element `A[i]`:
    - Increment its count in the `freq` array: `freq[A[i]]++`.
    - If its count becomes 2, it means this number has now been seen in both `A`'s and `B`'s prefixes. So, we increment `commonCount`.
- For the element `B[i]`:
    - Increment its count in the `freq` array: `freq[B[i]]++`.
    - If its count becomes 2, it means this number has now been seen in both `A`'s and `B`'s prefixes. So, we increment `commonCount`.
- Assign `C[i] = commonCount`.
- After the loop, return `C`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```