aboutsummaryrefslogtreecommitdiff
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
parent32b3c8cc7a72294298aabcedc2033b06f2a7ca5e (diff)
downloadleetcode-b7b7dd2713396b261a1ffd8be1c330c2fd828f9d.tar.gz
leetcode-b7b7dd2713396b261a1ffd8be1c330c2fd828f9d.zip
2657. find the prefix common array of the two arrays
-rw-r--r--find_prefix_common_arr.c43
-rw-r--r--find_prefix_common_arr.py33
2 files changed, 76 insertions, 0 deletions
diff --git a/find_prefix_common_arr.c b/find_prefix_common_arr.c
new file mode 100644
index 0000000..4e5fe05
--- /dev/null
+++ b/find_prefix_common_arr.c
@@ -0,0 +1,43 @@
+// 2657. Find the Prefix Common Array of Two Arrays
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+int *findThePrefixCommonArray(int *A, int ASize, int *B, int BSize,
+ int *returnSize) {
+ int *ans = (int *)malloc(ASize * sizeof(int)), cnt = 0;
+ int *vis = (int *)malloc((ASize + 1) * sizeof(int));
+ for (int i = 0; i < ASize; i++) {
+ if (++vis[A[i]] == 2)
+ cnt++;
+ if (++vis[B[i]] == 2)
+ cnt++;
+ ans[i] = cnt;
+ }
+ free(vis);
+ *returnSize = ASize;
+ return ans;
+}
+
+int main() {
+ int a1[] = {1, 2, 3, 4}, b1[] = {3, 1, 2, 4}, rs1;
+ int a2[] = {2, 3, 1}, b2[] = {3, 1, 2}, rs2;
+ int *ftpca1 =
+ findThePrefixCommonArray(a1, ARRAY_SIZE(a1), b1, ARRAY_SIZE(b1), &rs1);
+ int *ftpca2 =
+ findThePrefixCommonArray(a2, ARRAY_SIZE(a2), b2, ARRAY_SIZE(b2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", ftpca1[i]); // expect: 0 2 3 4
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", ftpca2[i]); // expect: 0 1 3
+ printf("\n");
+ free(ftpca1), free(ftpca2);
+}
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]))