Today’s problem

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/description/

Intuition

In this question, the only three ways that the answer will increase one is:

1. $A[i] == B[i]$.
2. $A[i]$ appears in $B$.
3. $B[i]$ appears in $A$.

Approach

• Iterate through the Array, then check for those three situation.
• Note that situation 1 conflicts with situation 2 & 3.
• That is, if cnt is add by 1 through situation 1, then situation 2 & 3 will not increase cnt.
• But situation 2 & 3 could increase cnt.

Complexity

• Time complexity: $O(N)$, N is the length of the list.

• Space complexity: $O(N)$, because we need to store a set.

Code

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        cntA = set([])
        cntB = set([])
        cnt = 0
        for i in range(len(A)):
            
            if A[i] == B[i]:
                cnt += 1
            else:
                if A[i] in cntB:
                    cnt += 1
                if B[i] in cntA:
                    cnt += 1
                cntA.add(A[i])
                cntB.add(B[i])
                
            ans.append(cnt)

        return ans