Find the Prefix Common Array of Two Arrays
MedPrompt
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 <= 501 <= A[i], B[i] <= nIt is guaranteed that A and B are both a permutation of n integers.
Approaches
3 approaches with complexity analysis and trade-offs.
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].
Algorithm
- Initialize an integer array
Cof sizen. - Loop with an index
ifrom0ton-1. - Inside the loop, create two hash sets,
setAandsetB. - Populate
setAwith elements fromA[0...i]. - Populate
setBwith elements fromB[0...i]. - Initialize a counter
commonCountto 0. - Iterate through the elements of
setA. For each element, check if it is present insetB. - 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.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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 toi.
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.
Algorithm
- Initialize an integer array
Cof sizen. - Initialize two empty hash sets,
setAandsetB. - Initialize a counter
commonCountto 0. - Loop with an index
ifrom0ton-1. - Let
valA = A[i]andvalB = B[i]. - If
valAis equal tovalB, it means a new number has appeared in both prefixes simultaneously. We incrementcommonCount. - If
valAis not equal tovalB:- Check if
valAis already present insetB. If so, addingvalAtosetAmakes it a new common element, so we incrementcommonCount. - Check if
valBis already present insetA. If so, addingvalBtosetBmakes it a new common element, so we incrementcommonCount.
- Check if
- Add
valAtosetAandvalBtosetB. - Assign
C[i] = commonCount. - After the loop, return
C.
Walkthrough
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.
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.
Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize an integer array
Cof sizen. - Initialize a frequency array
freqof sizen+1with all values as 0. - Initialize a counter
commonCountto 0. - Loop with an index
ifrom0ton-1. - For the element
A[i]:- Increment its count in the
freqarray:freq[A[i]]++. - If its count becomes 2, it means this number has now been seen in both
A's andB's prefixes. So, we incrementcommonCount.
- Increment its count in the
- For the element
B[i]:- Increment its count in the
freqarray:freq[B[i]]++. - If its count becomes 2, it means this number has now been seen in both
A's andB's prefixes. So, we incrementcommonCount.
- Increment its count in the
- Assign
C[i] = commonCount. - After the loop, return
C.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.