Count Values Shared by Both Prefixes at Each Position
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A and B are permutations of the integers 1 through n. Return an array C where C[i] counts values appearing somewhere in both prefixes A[0..i] and B[0..i]. Prefix positions are inclusive, and result coordinates follow increasing i.
```cpp
class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B);
};
```
### Examples
**Example 1:**
```text
Input: A = [2,1,3], B = [2,3,1]
Output: [1,1,3]
Explanation: The shared prefix values are first {2}, then {2}, and finally all three values.
```
**Example 2:**
```text
Input: A = [3,2,1], B = [1,2,3]
Output: [0,1,3]
Explanation: At the middle position only 2 is shared. At the end every value is shared.
```
### Constraints
- `1 <= A.length == B.length == n <= 50`.
- `1 <= A[i], B[i] <= n`.
- Each array contains every value from 1 through n exactly once.
### Clarifying Questions
- Which values appear in each input? Every integer from 1 through n exactly once.
- Are prefixes inclusive of index i? Yes.
- Must a common value be at the same position? No; it may appear anywhere within each prefix.
- What happens at the final index? Both full permutations contain all n values, so return n there.
```hint Check the boundary
Compare matching values at different positions with matching values at the same position.
```
Overview: Count values shared by both inclusive prefixes of two permutations at every position, returning the counts in index order.