Find the Prefix Common Array of Two Arrays

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.

def prefix_common_array(A, B):
    n = len(A)
    C = [0] * n
    common = set()
    for i in range(n):
        count = 0
        for j in range(i + 1):
            if A[j] in B[:i+1]:
                if A[j] not in common:
                    common.add(A[j])
                    count +=1
        C[i] = len(common)
    return C

# Example usage:
A = [1, 3, 2, 4]
B = [3, 1, 2, 4]
print(prefix_common_array(A, B))

A = [2,3,1]
B = [3,1,2]
print(prefix_common_array(A, B))

Explanation:

1. Initialization: The code initializes an array C of the same length as A and B, filled with zeros. This array will store the prefix common counts. It also creates an empty set called common to keep track of the unique common elements found so far.

2. Outer Loop: The outer loop iterates from i = 0 to n - 1, where n is the length of the arrays.

3. Inner Loop: The inner loop iterates from j = 0 to i, effectively considering the prefix of array A up to index i.

4. Checking for Common Elements: Inside the inner loop, it checks if the element A[j] is present in the prefix of array B up to index i (i.e., B[:i+1]).

5. Counting Unique Common Elements: If A[j] is found in the prefix of B, it checks if A[j] is already in the common set. If not, it adds A[j] to the common set and increments the count. This ensures that only unique common elements are counted.

6. Storing the Count: After the inner loop finishes, the code assigns the length of the common set (i.e., the number of unique common elements found up to index i) to C[i].

7. Returning the Result: Finally, the code returns the array C, which contains the prefix common counts.

Time and Space Complexity

Time Complexity: O(n^2) - Nested loops iterate through the arrays.

Space Complexity: O(n) - In the worst case, the common set might store all n elements if they are all common up to some point.