{"id":10027,"date":"2023-04-30T08:10:21","date_gmt":"2023-04-30T15:10:21","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10027"},"modified":"2023-04-30T08:17:54","modified_gmt":"2023-04-30T15:17:54","slug":"leetcode-2657-find-the-prefix-common-array-of-two-arrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2657-find-the-prefix-common-array-of-two-arrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2657. Find the Prefix Common Array of Two Arrays"},"content":{"rendered":"\n

You are given two 0-indexed <\/strong>integer <\/strong>permutations A<\/code> and B<\/code> of length n<\/code>.<\/p>\n\n\n\n

A prefix common array<\/strong> of A<\/code> and B<\/code> is an array C<\/code> such that C[i]<\/code> is equal to the count of numbers that are present at or before the index i<\/code> in both A<\/code> and B<\/code>.<\/p>\n\n\n\n

Return the prefix common array<\/strong> of <\/em>A<\/code> and <\/em>B<\/code>.<\/p>\n\n\n\n

A sequence of n<\/code> integers is called a permutation<\/strong> if it contains all integers from 1<\/code> to n<\/code> exactly once.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> A = [1,3,2,4], B = [3,1,2,4]\nOutput:<\/strong> [0,2,3,4]\nExplanation:<\/strong> At i = 0: no number is common, so C[0] = 0.\nAt i = 1: 1 and 3 are common in A and B, so C[1] = 2.\nAt i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.\nAt i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> A = [2,3,1], B = [3,1,2]\nOutput:<\/strong> [0,1,3]\nExplanation:<\/strong> At i = 0: no number is common, so C[0] = 0.\nAt i = 1: only 3 is common in A and B, so C[1] = 1.\nAt i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= A.length == B.length == n <= 50<\/code><\/li>
  • 1 <= A[i], B[i] <= n<\/code><\/li>
  • It is guaranteed that A and B are both a permutation of n integers.<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: Bitset<\/strong><\/h2>\n\n\n\n
    Use bitsets to store the numbers seen so far for each array, and use sA & sB to count the common elements.<\/p>\n\n\n\n
    Time complexity: O(n*50)
    Space complexity: O(50)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector findThePrefixCommonArray(vector& A, vector& B) {\n    bitset<51> sA;\n    bitset<51> sB;\n    vector ans;\n    for (int i = 0; i < A.size(); ++i) {\n      sA.set(A[i]);\n      sB.set(B[i]);\n      ans.push_back((sA & sB).count());\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Counter<\/strong><\/h2>\n\n\n\n
    Use a counter to track the frequency of each element, when the counter[x] == 2, we found a pair.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector findThePrefixCommonArray(vector& A, vector& B) {\n    vector count(A.size() + 1);\n    vector ans;\n    for (int i = 0, s = 0; i < A.size(); ++i) {\n      if (++count[A[i]] == 2) ++s;\n      if (++count[B[i]] == 2) ++s;\n      ans.push_back(s);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,232,187,177,97],"class_list":["post-10027","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-bitset","tag-mask","tag-medium","tag-prefix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10027","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10027"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10027\/revisions"}],"predecessor-version":[{"id":10031,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10027\/revisions\/10031"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10027"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10027"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10027"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}