diff options
author | Jack Sangdahl <[email protected]> | 2025-01-13 19:50:52 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-13 19:50:52 -0700 |
commit | b7b7dd2713396b261a1ffd8be1c330c2fd828f9d (patch) | |
tree | ccd547cb212151b164d41334b8d3406fffa28b92 /find_prefix_common_arr.py | |
parent | 32b3c8cc7a72294298aabcedc2033b06f2a7ca5e (diff) | |
download | leetcode-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.py | 33 |
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])) |