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.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.
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.
Time Complexity: O(n), since it iterates through the arrays once. Space Complexity: O(n), due to the arrays used for tracking seen elements.
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.
Time Complexity: O(n). Space Complexity: O(n).
| 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). |
| 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 |
Find the Prefix Common Array of Two Arrays | 3 Detailed Approach | Leetcode 2657 | codestorywithMIK • codestorywithMIK • 6,870 views views
Watch 9 more video solutions →Practice Find the Prefix Common Array of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode