The goal was to calculate the count of common elements between the two permutations (A) and (B) at or before each index (i), and store these counts in the array (c).
In this approach, I used three sets: seen_a, seen_b, and common. The seen_a set kept track of the elements from (A) that had been encountered up to the current index, while seen_b did the same for (B). The common set was used to store elements that were present in both (A) and (B).
For each index (i), I started by adding the current elements (A[i]) and (B[i]) to their sets (seen_a and seen_b). Then, I checked if (A[i]) was already in seen_b or if (B[i]) was already in seen_a. If either condition was true, I added the element to the common set, signifying that it was present in both arrays.
After updating the common set, I calculated its size, which represented the count of common elements up to the current index. I appended this count to the result array (c) and returned array (c).
class Solution:
def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
n = len(A)
c = []
seen_a = set()
seen_b = set()
common = set()
for i in range(n):
seen_a.add(A[i])
seen_b.add(B[i])
if A[i] in seen_b:
common.add(A[i])
if B[i] in seen_a:
common.add(B[i])
c.append(len(common))
return c- Time: O(n), where n is the length of the arrays A and B.
- Space: O(n), for storing the
seenset.
