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 ofAandB.
A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.
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:
1
2
3
4
5
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 3is 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.
In a brute force approach, we can simply iterate through all indices and at each index, count how many elements from the beginning to the current index are common in both permutations A and B.
Here is the approach:
Initialize an array C of size n with all elements as 0.
Iterate through each index i from 0 to n-1:
Initialize a counter common_count to 0.
For each element up to the current index i (i.e. from 0 to i inclusive) in both arrays:
Check if the element at the current position in A is present in the prefix of B up to the current index i.
function findThePrefixCommonArray(A, B):
n = length of A
C = array of size n filled with0for i from0 to n-1:
common_count =0for j from0 to i:
if A[j] in B[0 to i]:
common_count +=1 C[i] = common_count
return C
classSolution {
publicint[]findThePrefixCommonArray(int[] A, int[] B) {
int n = A.length;
int[] C =newint[n];
for (int i = 0; i < n; i++) {
int commonCount = 0;
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= i; k++) {
if (A[j]== B[k]) {
commonCount++;
break; // Avoid counting the same element multiple times }
}
}
C[i]= commonCount;
}
return C;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution:
deffindThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
n = len(A)
C: List[int] = [0] * n
for i in range(n):
common_count =0for j in range(i+1):
if A[j] in B[:i+1]:
common_count +=1 C[i] = common_count
return C
classSolution {
publicint[]findThePrefixCommonArray(int[] A, int[] B) {
int n = A.length;
int[] ans =newint[n];
Set<Integer> setA =new HashSet<>();
Set<Integer> setB =new HashSet<>();
for (int i = 0; i < n; i++) {
setA.add(A[i]);
setB.add(B[i]);
int common = 0;
for (int a : setA) {
if (setB.contains(a)) {
common++;
}
}
ans[i]= common;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution:
deffindThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
n = len(A)
ans: List[int] = [0] * n
set_a: Set[int] = set()
set_b: Set[int] = set()
for i in range(n):
set_a.add(A[i])
set_b.add(B[i])
common =0for a in set_a:
if a in set_b:
common +=1 ans[i] = common
return ans
⏰ Time complexity: O(n^2) in the worst case because for each index i, we might perform a set intersection which can take up to O(i) comparisons cumulatively.
🧺 Space complexity: O(n) for storing the numbers we’ve seen in both A and B.
To determine the prefix common array C[i], we need to count how many numbers are common in both arrays A and B up to index i.
Key Observations:
Both A and B are permutations, meaning all integers from 1 to n are present exactly once.
We can use an frequency array to track the frequency of the element structure to track which elements have been encountered in both arrays.
We need to count common element in A and B upto an index.
So, for each element in A and B, we increment its corresponding counter in cnt. If the frequency of that element reaches 2, it indicates the element is found in both arrays up to the current index i.
classSolution {
publicint[]findThePrefixCommonArray(int[] A, int[] B) {
int n = A.length;
int[] freq =newint[n + 1]; // Auxiliary array to track frequenciesint[] ans =newint[n]; // Result arrayint common = 0; // Count of common elementsfor (int i = 0; i < n; i++) {
// Increment frequency of A[i]; if it reaches 2, increment common countif (++freq[A[i]]== 2) {
common++;
}
// Increment frequency of B[i]; if it reaches 2, increment common countif (++freq[B[i]]== 2) {
common++;
}
ans[i]= common; // Store common count up to index i }
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution:
deffindThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
n = len(A)
freq = [0] * (n +1) # Auxiliary array to track frequencies ans = [0] * n # Result array common =0# Count of common elementsfor i in range(n):
# Increment frequency of A[i]; if it reaches 2, increment common countif (freq[A[i]] := freq[A[i]] +1) ==2:
common +=1# Increment frequency of B[i]; if it reaches 2, increment common countif (freq[B[i]] := freq[B[i]] +1) ==2:
common +=1 ans[i] = common # Store common count up to index ireturn ans