aboutsummaryrefslogtreecommitdiff
path: root/find_prefix_common_arr.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-13 19:50:52 -0700
committerJack Sangdahl <[email protected]>2025-01-13 19:50:52 -0700
commitb7b7dd2713396b261a1ffd8be1c330c2fd828f9d (patch)
treeccd547cb212151b164d41334b8d3406fffa28b92 /find_prefix_common_arr.py
parent32b3c8cc7a72294298aabcedc2033b06f2a7ca5e (diff)
downloadleetcode-b7b7dd2713396b261a1ffd8be1c330c2fd828f9d.tar.gz
leetcode-b7b7dd2713396b261a1ffd8be1c330c2fd828f9d.zip
2657. find the prefix common array of the two arrays
Diffstat (limited to 'find_prefix_common_arr.py')
-rw-r--r--find_prefix_common_arr.py33
1 files changed, 33 insertions, 0 deletions
diff --git a/find_prefix_common_arr.py b/find_prefix_common_arr.py
new file mode 100644
index 0000000..ccce100
--- /dev/null
+++ b/find_prefix_common_arr.py
@@ -0,0 +1,33 @@
+# 2657. Find the Prefix Common Array of Two Arrays
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def findThePrefixCommonArray(self, A, B):
+ """
+ :type A: List[int]
+ :type B: List[int]
+ :rtype: List[int]
+ """
+ ans, vis, cnt = [], 0, 0
+ for ab in zip(A, B):
+ for a in ab:
+ if (1 << a) & vis:
+ cnt += 1
+ vis |= 1 << a
+ ans.append(cnt)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findThePrefixCommonArray(A=[1, 3, 2, 4], B=[3, 1, 2, 4]))
+ print(obj.findThePrefixCommonArray(A=[2, 3, 1], B=[3, 1, 2]))