Find the Prefix Common Array of Two Arrays

Problem Description

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.

Key Insights

• The problem requires counting common elements at each index from both arrays.
• Both arrays are permutations, which means they contain all integers from 1 to n exactly once.
• A straightforward approach is to use a set to track common elements as we iterate through the arrays.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a set to keep track of the numbers we have seen in both arrays as we iterate through them. For each index i, we count how many numbers have been seen in both A and B up to that index. The algorithm proceeds as follows:

1. Initialize a set to store common numbers.
2. Initialize an array C to store the prefix counts.
3. Iterate through both arrays simultaneously:
   • Add numbers from A and B to the set.
   • Count how many numbers are in the set that belong to both A and B and store that count in C.
4. Return the array C.

Code Solutions