Find the Prefix Common Array of Two Arrays — Solution
Find the Prefix Common Array of Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Prefix Common Array of Two Arrays is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
a and b are both permutations of the integers 1 to n. Their prefix common array is the array c of length n where c[i] is the number of values that appear in both a[0..i] and b[0..i].
Return c.
Example 1
Input: a = [2,4,1,3], b = [4,1,2,3]
Output: [0,1,3,4]
Explanation: After index 1 only `4` is shared; after index 2 the prefixes hold `{1,2,4}` each.
Example 2
Input: a = [3,1,2], b = [3,2,1]
Output: [1,1,3]
Constraints
1 <= a.length == b.length == n <= 501 <= a[i], b[i] <= na and b are permutations of 1..n
Hints for Find the Prefix Common Array of Two Arrays
Hint 1
Recomputing the intersection for every prefix is O(n²) — fine for these limits, but there is a one-pass way.
Hint 2
Each value appears once in each array, so it becomes common exactly when its second occurrence (in either array) has been seen.
Hint 3
Keep a count per value; when a count reaches 2, the number of common values grows by one.
How to solve Find the Prefix Common Array of Two Arrays
A value joins the common set at the moment both arrays have shown it — that is, the second time it is seen across the two prefixes. Counting sightings per value turns the prefix intersection into a running counter.
Approach
- Keep
seen[v]forv = 1..n, all 0, andcommon = 0. - For each
i: incrementseen[a[i]]; if it became 2, incrementcommon. - Do the same for
b[i]. - Set
c[i] = common.
Why it works
Within one permutation a value occurs once, so seen[v] = 2 means v is in both prefixes, and that transition happens exactly once per value, at the first index where both prefixes contain it. Hence common always equals the size of the intersection.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Process both
a[i]andb[i]before recordingc[i]— whena[i] == b[i]the value counts at indexi. - The answer is non-decreasing and ends at
n; a quick sanity check. - A bitmask (
n <= 50fits in 64 bits) also works, but the counting array is simpler.
Reference solution
Python
from typing import List
def findThePrefixCommonArray(a: List[int], b: List[int]) -> List[int]:
n = len(a)
seen = [0] * (n + 1)
common = 0
res = []
for i in range(n):
seen[a[i]] += 1
if seen[a[i]] == 2:
common += 1
seen[b[i]] += 1
if seen[b[i]] == 2:
common += 1
res.append(common)
return resJava
public static int[] findThePrefixCommonArray(int[] a, int[] b) {
int n = a.length;
int[] seen = new int[n + 1];
int[] res = new int[n];
int common = 0;
for (int i = 0; i < n; i++) {
if (++seen[a[i]] == 2) common++;
if (++seen[b[i]] == 2) common++;
res[i] = common;
}
return res;
}C++
vector<int> findThePrefixCommonArray(vector<int>& a, vector<int>& b) {
int n = a.size();
vector<int> seen(n + 1, 0), res(n);
int common = 0;
for (int i = 0; i < n; i++) {
if (++seen[a[i]] == 2) common++;
if (++seen[b[i]] == 2) common++;
res[i] = common;
}
return res;
}JavaScript
var findThePrefixCommonArray = function(a, b) {
var n = a.length;
var seen = new Array(n + 1).fill(0);
var common = 0, res = [];
for (var i = 0; i < n; i++) {
if (++seen[a[i]] === 2) common++;
if (++seen[b[i]] === 2) common++;
res.push(common);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets