Find the Prefix Common Array of Two Arrays

Find the Prefix Common Array of Two Arrays

1. What is this problem about?

The Find the Prefix Common Array of Two Arrays interview question asks you to find the cumulative count of common elements between two permutations as you move from left to right. You are given two arrays, $A$ and $B$, which are permutations of numbers from $1$ to $n$. For each index $i$, you need to determine how many elements are present in both $A[0 \dots i]$ and $B[0 \dots i]$.

2. Why is this asked in interviews?

Companies like Yandex and Meta use the Find the Prefix Common Array coding problem to assess a candidate's ability to maintain state efficiently. It tests your knowledge of Hash Table interview patterns and frequency counting. It evaluations if you can solve the problem in $O(N)$ time by updating the count of common elements incrementally instead of re-scanning the prefixes at each index.

3. Algorithmic pattern used

This problem follows the Frequency Counting and State Tracking pattern.

• Count Map: Maintain an array or hash map to count the occurrences of each number seen so far in both $A$ and $B$.
• Common Count: Keep a running total common_so_far.
• Logic: At index $i$, increment the count for A[i] and B[i].
  • If incrementing the count for A[i] makes it 2, then A[i] has now appeared in both prefixes. Increment common_so_far.
  • If A[i] and B[i] are different, also check if incrementing the count for B[i] makes it 2. If so, increment common_so_far.
  • If A[i] == B[i], they both contribute to the same increment.

4. Example explanation

$A = [1, 3, 2, 4], B = [3, 1, 2, 4]$

• $i=0$: $A[0]=1, B[0]=3$. Counts: {1:1, 3:1}. Common = 0.
• $i=1$: $A[1]=3, B[1]=1$. Counts: {1:2, 3:2}. Both reached count 2. Common = 2.
• $i=2$: $A[2]=2, B[2]=2$. Counts: {1:2, 3:2, 2:2}. 2 reached count 2. Common = 3.
• $i=3$: $A[3]=4, B[3]=4$. Counts: {1:2, 3:2, 2:2, 4:2}. 4 reached count 2. Common = 4. Result: [0, 2, 3, 4].

5. Common mistakes candidates make

• $O(N^2)$ Re-scanning: Comparing the two prefixes from scratch at every index. This is inefficient for large $n$.
• Off-by-one: Counting the same number twice in the common count if $A[i] == B[i]$.
• Incorrect initialization: Forgetting to handle the very first index correctly.

6. Interview preparation tip

Always look for ways to update a result based on the previous result. This "Running State" optimization is a fundamental skill in Array interview patterns and saves significant computation time.