Find the Prefix Common Array of Two Arrays - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given two arrays A and B, both permutations of numbers from 1..n. For each index i, compute how many values appear in both prefixes A[0..i] and B[0..i]. The result is the prefix common array where result[i] stores that count.
Approach 1: Using Two Sets to Track Common Elements (Time: O(n), Space: O(n))
This approach maintains two hash sets that store elements seen so far in each prefix. As you iterate index i from 0 to n-1, insert A[i] into the first set and B[i] into the second. After each insertion, check whether the newly added values exist in the opposite set using constant-time hash lookups. Every time a match is found, increment the running count of common elements and store it in the result array. The key insight is that an element becomes "prefix common" exactly when it has appeared in both prefixes. Hash sets make these membership checks O(1), giving an overall O(n) traversal. This approach is easy to reason about and works well whenever fast membership checks are needed using a hash table.
Approach 2: Using a Single Array to Track Presence (Time: O(n), Space: O(n))
Since both arrays are permutations of 1..n, you can replace hash sets with a simple counting array. Maintain an integer array freq of size n + 1. For each index i, increment freq[A[i]] and freq[B[i]]. When a value's count becomes 2, it means the element has appeared in both prefixes, so you increase the common counter. Store the running count in the result. This works because every value appears exactly once in each array, so the second occurrence signals a match. The approach avoids hash structures and uses direct indexing, which is faster in practice. The idea resembles techniques used in array counting problems and sometimes pairs nicely with bit manipulation optimizations when memory is tightly controlled.
Recommended for interviews: The single-array presence approach is typically preferred. It exploits the permutation constraint and produces a clean O(n) solution with minimal overhead. Interviewers often expect you to first reason about tracking seen elements (the two-set idea) and then optimize it by replacing hash structures with an indexed array.
Approach 1: Using Two Sets to Track Common Elements
This approach involves two sets to track elements of A and B as you traverse them. For each index i, you will check how many elements have been seen in both sets. This allows us to efficiently count common elements at each index.
The solution uses two arrays 'seenA' and 'seenB' to keep track of which numbers from 1 to n have been encountered in arrays A and B respectively. For each element in the arrays, it updates the 'seenA' and 'seenB' arrays and then checks if the element has been seen in both. This allows counting how many numbers have been seen in both arrays up to index i.
Complexity
Time Complexity: O(n), since it iterates through the arrays once. Space Complexity: O(n), due to the arrays used for tracking seen elements.
Approach 2: Using a Single Array to Track Presence
This approach utilizes a single integer array of length n+1 to track occurrences. As you iterate, you update this array for presence in A and B. The count of elements present in both arrays is updated based on the state of this tracking array.
This solution employs a single integer array 'occurrence' to maintain a count of numbers observed from both arrays. For each number from A and B, it increments the respective index in 'occurrence'. If that index's value becomes 2, it indicates that the number has appeared in both arrays.
Complexity
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Counting
We can use two arrays cnt1 and cnt2 to record the occurrence times of each element in arrays A and B respectively, and use an array ans to record the answer.
Traverse arrays A and B, increment the occurrence times of A[i] in cnt1, and increment the occurrence times of B[i] in cnt2. Then enumerate j \in [1,n], calculate the minimum occurrence times of each element j in cnt1 and cnt2, and accumulate them into ans[i].
After the traversal, return the answer array ans.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of arrays A and B.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Bit Operation (XOR Operation)
We can use an array vis of length n+1 to record the occurrence situation of each element in arrays A and B, the initial value of array vis is 1. In addition, we use a variable s to record the current number of common elements.
Next, we traverse arrays A and B, update vis[A[i]] = vis[A[i]] \oplus 1, and update vis[B[i]] = vis[B[i]] \oplus 1, where \oplus represents XOR operation.
If at the current position, the element A[i] has appeared twice (i.e., it has appeared in both arrays A and B), then the value of vis[A[i]] will be 1, and we increment s. Similarly, if the element B[i] has appeared twice, then the value of vis[B[i]] will be 1, and we increment s. Then add the value of s to the answer array ans.
After the traversal, return the answer array ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of arrays A and B.
Code
Python
Java
C++
Go
TypeScript
Approach 5: Bit Manipulation (Space Optimization)
Since the elements of arrays A and B are in the range [1, n] and do not exceed 50, we can use an integer x and an integer y to represent the occurrence of each element in arrays A and B, respectively. Specifically, we use the i-th bit of integer x to indicate whether element i has appeared in array A, and the i-th bit of integer y to indicate whether element i has appeared in array B.
The time complexity of this solution is O(n), where n is the length of arrays A and B. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Two Sets to Track Common Elements | Time Complexity: O(n), since it iterates through the arrays once. Space Complexity: O(n), due to the arrays used for tracking seen elements. |
| Using a Single Array to Track Presence | Time Complexity: O(n). Space Complexity: O(n). |
| Counting | — |
| Bit Operation (XOR Operation) | — |
| Bit Manipulation (Space Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Sets to Track Common Elements | O(n) | O(n) | General solution when arrays may not be permutations or when hash-based membership checks are preferred |
| Single Array Presence Tracking | O(n) | O(n) | Best when values are in range 1..n; avoids hash tables and runs faster in practice |
Video Solution
Find the Prefix Common Array of Two Arrays | 3 Detailed Approach | Leetcode 2657 | codestorywithMIK • codestorywithMIK • 9,595 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Prefix Common Array of Two Arrays easy or hard?
Find the Prefix Common Array of Two Arrays Python/Java solution
How to solve Find the Prefix Common Array of Two Arrays in O(n)?
What is the best approach for Find the Prefix Common Array of Two Arrays?
Is Find the Prefix Common Array of Two Arrays asked at Google/Amazon/Meta?
What data structure is used in Find the Prefix Common Array of Two Arrays?
What is the time complexity of Find the Prefix Common Array of Two Arrays?
Ready to solve this problem?
Practice Find the Prefix Common Array of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode