2657. Find the Prefix Common Array of Two Arrays LeetCode Solution
In this guide, you will get 2657. Find the Prefix Common Array of Two Arrays LeetCode Solution with the best time and space complexity. The solution to Find the Prefix Common Array of Two Arrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2657. Find the Prefix Common Array of Two Arrays LeetCode Solution in C++
class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
const int n = A.size();
int prefixCommon = 0;
vector<int> ans;
vector<int> count(n + 1);
for (int i = 0; i < A.size(); ++i) {
if (++count[A[i]] == 2)
++prefixCommon;
if (++count[B[i]] == 2)
++prefixCommon;
ans.push_back(prefixCommon);
}
return ans;
}
}; /* code provided by PROGIEZ */
2657. Find the Prefix Common Array of Two Arrays LeetCode Solution in Java
class Solution {
public int[] findThePrefixCommonArray(int[] A, int[] B) {
final int n = A.length;
int prefixCommon = 0;
int[] ans = new int[n];
int[] count = new int[n + 1];
for (int i = 0; i < A.length; ++i) {
if (++count[A[i]] == 2)
++prefixCommon;
if (++count[B[i]] == 2)
++prefixCommon;
ans[i] = prefixCommon;
}
return ans;
}
} // code provided by PROGIEZ
2657. Find the Prefix Common Array of Two Arrays LeetCode Solution in Python
class Solution:
def findThePrefixCommonArray(self, A: list[int], B: list[int]) -> list[int]:
n = len(A)
prefixCommon = 0
ans = []
count = [0] * (n + 1)
for a, b in zip(A, B):
count[a] += 1
if count[a] == 2:
prefixCommon += 1
count[b] += 1
if count[b] == 2:
prefixCommon += 1
ans.append(prefixCommon)
return ans # code by PROGIEZ
