Problem Statement in English

You’re given two 0-indexed integer arrays A and B of length n. The common array of A and B is an array C of length n where:

  • C[i] is the number of common elements in the prefix of A and B upto and including the current index i.

Return the common array of A and B.

Approach

We can maintain two hash maps to count the frequency of elements in both arrays.

We can iterate through both arrays simultaneously and update the counts in the hash maps.

Now there are 2 ways it can go:

  • If the current elements of both arrays are the same and their counts in both hash maps are also the same, then we can increment the count of common elements by 1.

  • If the current elements of both arrays are different, then we can check if the count of the current element in the first array is equal to its count in the second array. If it is, then we can increment the count of common elements by 1. We can do the same for the current element in the second array.

Also remember to add the count of common elements from the previous index to the current index in the result array.

And we’re done!

Solution in Python


class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        res = [0] * n
        ca = defaultdict(int)
        cb = defaultdict(int)

        for i in range(n):
            ca[A[i]] += 1
            cb[B[i]] += 1
            temp = 0

            if A[i] == B[i] and ca[A[i]] == cb[B[i]]:
                temp += 1
            else:
                if ca[A[i]] == cb[A[i]]:
                    temp += 1
                if ca[B[i]] == cb[B[i]]:
                    temp += 1

            if i - 1 >= 0:
                res[i] += res[i - 1]
            
            res[i] += temp

        return res

Complexity

  • Time: $O(n)$
    Since we traverse the array once.

  • Space: $O(n)$
    Since we store the count of elements in both arrays.

And we are done.