Problem

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.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Examples

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

  • 1 <= A.length == B.length == n <= 50
  • 1 <= A[i], B[i] <= n
  • It is guaranteed that A and B are both a permutation of n integers.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive

In a brute force approach, we can simply iterate through all indices and at each index, count how many elements from the beginning to the current index are common in both permutations A and B.

Here is the approach:

  1. Initialize an array C of size n with all elements as 0.
  2. Iterate through each index i from 0 to n-1:
    • Initialize a counter common_count to 0.
    • For each element up to the current index i (i.e. from 0 to i inclusive) in both arrays:
      • Check if the element at the current position in A is present in the prefix of B up to the current index i.
      • If it is, increment the common_count.
    • Store the value of common_count in C[i].
  3. Return the array C.

Pseudocode

function findThePrefixCommonArray(A, B):
    n = length of A
    C = array of size n filled with 0
    
    for i from 0 to n-1:
        common_count = 0
        for j from 0 to i:
            if A[j] in B[0 to i]:
                common_count += 1
        C[i] = common_count
    
    return C

Code

Java
class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] C = new int[n];
        
        for (int i = 0; i < n; i++) {
            int commonCount = 0;
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k <= i; k++) {
                    if (A[j] == B[k]) {
                        commonCount++;
                        break; // Avoid counting the same element multiple times
                    }
                }
            }
            C[i] = commonCount;
        }
        return C;
    }
}
Python
class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        C: List[int] = [0] * n
        
        for i in range(n):
            common_count = 0
            for j in range(i+1):
                if A[j] in B[:i+1]:
                    common_count += 1
            C[i] = common_count
        
        return C

Method 2 - Using Set

Understanding the problem:

  • We have two permutations A and B of length n.
  • A permutation means each integer from 1 to n appears exactly once.
  • We need to create an array C such that for each index i, C[i] contains the count of numbers that appear in both A and B up to and including index i.

Approach

  • We can use sets to keep track of the numbers we have encountered so far in both permutations.
  • For each index i, we check how many elements in the current prefix of A are also in the current prefix of B.
  • This can be efficiently done using set intersection.

Code

Java
class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] ans = new int[n];
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setB = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            setA.add(A[i]);
            setB.add(B[i]);
            int common = 0;
            for (int a : setA) {
                if (setB.contains(a)) {
                    common++;
                }
            }
            ans[i] = common;
        }
        return ans;
    }
}
Python
class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        ans: List[int] = [0] * n
        set_a: Set[int] = set()
        set_b: Set[int] = set()
        
        for i in range(n):
            set_a.add(A[i])
            set_b.add(B[i])
            common = 0
            for a in set_a:
                if a in set_b:
                    common += 1
            ans[i] = common
        
        return ans

Complexity

  • ⏰ Time complexity: O(n^2) in the worst case because for each index i, we might perform a set intersection which can take up to O(i) comparisons cumulatively.
  • 🧺 Space complexity: O(n) for storing the numbers we’ve seen in both A and B.

Method 3 - Using Frequency array

To determine the prefix common array C[i], we need to count how many numbers are common in both arrays A and B up to index i.

Key Observations:

  • Both A and B are permutations, meaning all integers from 1 to n are present exactly once.
  • We can use an frequency array to track the frequency of the element structure to track which elements have been encountered in both arrays.
  • We need to count common element in A and B upto an index.
  • So, for each element in A and B, we increment its corresponding counter in cnt. If the frequency of that element reaches 2, it indicates the element is found in both arrays up to the current index i.

Code

Java
class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] freq = new int[n + 1]; // Auxiliary array to track frequencies
        int[] ans = new int[n]; // Result array
        int common = 0; // Count of common elements

        for (int i = 0; i < n; i++) {
            // Increment frequency of A[i]; if it reaches 2, increment common count
            if (++freq[A[i]] == 2) {
	            common++;
	        }
            // Increment frequency of B[i]; if it reaches 2, increment common count
            if (++freq[B[i]] == 2) {
	            common++;
	        }
            ans[i] = common; // Store common count up to index i
        }
        return ans;
    }
}
Python
class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        freq = [0] * (n + 1) # Auxiliary array to track frequencies
        ans = [0] * n # Result array
        common = 0 # Count of common elements

        for i in range(n):
            # Increment frequency of A[i]; if it reaches 2, increment common count
            if (freq[A[i]] := freq[A[i]] + 1) == 2:
                common += 1
            
            # Increment frequency of B[i]; if it reaches 2, increment common count
            if (freq[B[i]] := freq[B[i]] + 1) == 2:
                common += 1
                
            ans[i] = common # Store common count up to index i
        
        return ans

Complexity

  • ⏰ Time complexity: O(n) since we are iterating through the arrays once.
  • 🧺 Space complexity: O(n) since we are iterating through the arrays once.