Watch 10 video solutions for Find the Prefix Common Array of Two Arrays, a medium level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by codestorywithMIK has 6,870 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |