Problem Description

You are given two permutations A and B, both containing integers from 1 to n exactly once. These are 0-indexed arrays of length n.

Your task is to find the prefix common array C for these two permutations.

For each position i in the result array C:

• C[i] represents the count of numbers that appear in both A[0...i] and B[0...i]
• In other words, C[i] counts how many distinct numbers are present in both arrays up to and including index i

Example walkthrough:

If A = [3, 1, 2] and B = [2, 3, 1]:

• At index 0: A[0] = 3, B[0] = 2. No common numbers yet, so C[0] = 0
• At index 1: A[0...1] = [3, 1], B[0...1] = [2, 3]. Number 3 appears in both, so C[1] = 1
• At index 2: A[0...2] = [3, 1, 2], B[0...2] = [2, 3, 1]. All three numbers (1, 2, 3) appear in both, so C[2] = 3

The result would be C = [0, 1, 3].

The solution uses two counters to track the frequency of elements seen so far in each array. At each position i, it counts elements by finding the minimum occurrence of each number between the two counters - if a number has appeared in both arrays up to position i, the minimum will be at least 1, contributing to the count.

Intuition

The key insight is that we need to track which numbers have appeared in both arrays up to each position. Since we're dealing with permutations (each number from 1 to n appears exactly once), we know that each number will eventually appear in both arrays.

Think of it this way: as we traverse both arrays simultaneously, we're gradually "collecting" numbers from each array. A number contributes to our count only when it has been seen in both arrays.

This naturally leads us to use counting/frequency tracking. For each position i:

• We keep track of all numbers we've seen so far in array A
• We keep track of all numbers we've seen so far in array B
• A number is "common" at position i if it has appeared at least once in both tracking structures

The clever part is using min(cnt1[x], cnt2[x]) for each number x. Since we're dealing with permutations where each number appears exactly once:

• If a number hasn't appeared in one array yet, min will be 0
• If a number has appeared in both arrays, min will be 1
• The sum of all these minimums gives us the total count of common numbers

For example, if by position i, array A has seen {1, 3, 5} and array B has seen {2, 3, 5}, then:

• Number 1: min(1, 0) = 0 (only in A)
• Number 2: min(0, 1) = 0 (only in B)
• Number 3: min(1, 1) = 1 (in both)
• Number 5: min(1, 1) = 1 (in both)
• Total common = 0 + 0 + 1 + 1 = 2

This approach efficiently solves the problem in a single pass through both arrays.

Solution Approach

The implementation uses a counting approach with two hash maps (Counter objects in Python) to track the occurrences of elements in both arrays.

Step-by-step implementation:

1. Initialize data structures:

   • Create an empty result array ans to store the prefix common counts
   • Initialize two Counter objects cnt1 and cnt2 to track element frequencies for arrays A and B respectively

2. Traverse both arrays simultaneously:

   • Use zip(A, B) to iterate through both arrays in parallel, getting elements a from A and b from B at each position

3. Update counters at each position:

   • Increment cnt1[a] to record that element a has been seen in array A
   • Increment cnt2[b] to record that element b has been seen in array B

4. Calculate common count:

   • For each element x that exists in cnt1, compute min(cnt1[x], cnt2[x])
   • This gives us 1 if element x has appeared in both arrays, 0 otherwise
   • Sum all these minimum values: t = sum(min(v, cnt2[x]) for x, v in cnt1.items())

5. Store and continue:

   • Append the calculated count t to the result array ans
   • Continue this process for all positions in the arrays

6. Return the result:

   • After processing all positions, return the complete ans array

Why this works:

• Since we're dealing with permutations, each number appears exactly once in each array
• At any position i, a number contributes to the count if and only if it has appeared in both arrays up to that position
• The min operation effectively checks if a number exists in both counters (returning 1 if yes, 0 if no)
• The sum aggregates all common numbers at the current position

Time Complexity: O(n²) in the worst case, as for each of the n positions, we might iterate through up to n elements in cnt1

Space Complexity: O(n) for storing the counters and result array

Example Walkthrough

Let's walk through a concrete example with A = [2, 3, 1] and B = [3, 1, 2].

We'll track two counters and build our result array step by step:

Initial state:

• cnt1 = {} (tracks elements seen in A)
• cnt2 = {} (tracks elements seen in B)
• ans = []

Position 0:

• Process: a = 2, b = 3
• Update counters: cnt1 = {2: 1}, cnt2 = {3: 1}
• Calculate common count:
  • Element 2: min(1, 0) = 0 (2 is in A but not in B)
  • Total = 0
• Append to result: ans = [0]

Position 1:

• Process: a = 3, b = 1
• Update counters: cnt1 = {2: 1, 3: 1}, cnt2 = {3: 1, 1: 1}
• Calculate common count:
  • Element 2: min(1, 0) = 0 (only in A)
  • Element 3: min(1, 1) = 1 (in both A and B!)
  • Total = 0 + 1 = 1
• Append to result: ans = [0, 1]

Position 2:

• Process: a = 1, b = 2
• Update counters: cnt1 = {2: 1, 3: 1, 1: 1}, cnt2 = {3: 1, 1: 1, 2: 1}
• Calculate common count:
  • Element 2: min(1, 1) = 1 (now in both!)
  • Element 3: min(1, 1) = 1 (still in both)
  • Element 1: min(1, 1) = 1 (now in both!)
  • Total = 1 + 1 + 1 = 3
• Append to result: ans = [0, 1, 3]

Final result: [0, 1, 3]

Notice how at each position, we only count elements that have appeared in BOTH arrays up to that point. The min operation elegantly handles this - returning 1 only when an element exists in both counters, and 0 otherwise.

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), and the space complexity is O(n).

Time Complexity Analysis:

• The outer loop iterates through both arrays A and B simultaneously using zip, which runs n times where n is the length of the arrays.
• Inside each iteration:
  • Updating cnt1[a] and cnt2[b] takes O(1) time.
  • The key operation is sum(min(v, cnt2[x]) for x, v in cnt1.items()), which iterates through all items in cnt1.
  • In the worst case, after processing i elements, cnt1 contains i unique elements.
  • Therefore, at iteration i, this sum operation takes O(i) time.
• The total time complexity is O(1) + O(2) + O(3) + ... + O(n) = O(n(n+1)/2) = O(n²).

Space Complexity Analysis:

• Two Counter objects cnt1 and cnt2 are created to store the frequency of elements.
• In the worst case, all elements in arrays A and B are unique, so each Counter can store up to n key-value pairs.
• The ans list stores n results.
• Therefore, the total space complexity is O(n) + O(n) + O(n) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Iteration Over All Counter Elements

The Pitfall: The current solution iterates through all elements in frequency_a at each position, even though most elements haven't appeared yet. Since we're processing permutations of numbers 1 to n, early in the iteration, most counter entries are zero, making the iteration unnecessarily expensive.

Why It's Problematic:

• At position i, we're iterating through up to i+1 elements in the counter
• This leads to O(n²) time complexity even though we could optimize further
• We're checking elements that we know haven't appeared in array A yet

Optimized Solution: Instead of iterating through the entire counter, we can track common elements more efficiently by checking only when an element appears in both arrays:

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        result = []
        seen_a = set()
        seen_b = set()
        common_count = 0
      
        for element_a, element_b in zip(A, B):
            # Add current elements to their respective sets
            seen_a.add(element_a)
            seen_b.add(element_b)
          
            # Check if the new elements create new common elements
            if element_a in seen_b:
                common_count += 1
            if element_b in seen_a and element_a != element_b:
                common_count += 1
          
            result.append(common_count)
      
        return result

2. Using Counter When Sets Would Suffice

The Pitfall: Since we're dealing with permutations where each element appears exactly once, using Counters adds unnecessary overhead. The frequency will always be either 0 or 1.

Why It's Problematic:

• Counter objects have more overhead than sets
• The min operation is redundant since values are always 0 or 1
• We're essentially using Counters as expensive sets

Better Approach: Use sets to track which elements have been seen, making the logic clearer and more efficient:

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        result = []
        seen_a = set()
        seen_b = set()
      
        for element_a, element_b in zip(A, B):
            seen_a.add(element_a)
            seen_b.add(element_b)
          
            # Count intersection size directly
            common_count = len(seen_a & seen_b)
            result.append(common_count)
      
        return result

This approach:

• Reduces time complexity to O(n) average case for set operations
• Uses less memory with sets instead of Counters
• Makes the intent clearer - we're finding intersection of two sets