#2657

Find the Prefix Common Array of Two Arrays

pupil · 385 · lc medium +24 · verified · 87% accepted · 1,154 likes · top 98%

Description

You are given two 0-indexed integer permutations A and B of length n. Build the prefix common array C where C[i] is the count of integers that appear in both A[0..i] and B[0..i]. Return C.

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.

Code

1

2

3

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]: