2657. Find the Prefix Common Array of Two Arrays

Method 1

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.

Example 1

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Method 1

【O(n) time | O(n) space】

package Leetcode.Math;

import java.util.Arrays;

/**
 * @author zhengxingxing
 * @date 2025/01/14
 */
public class FindThePrefixCommonArrayOfTwoArrays {
    public static int[] findThePrefixCommonArray(int[] a, int[] b) {
        int n = a.length;
        int[] ans = new int[n]; // Result array
        long p = 0, q = 0;     // Bitmaps representing elements in a and b

        for (int i = 0; i < n; ++i) {
            p |= 1L << a[i];     // Set the bit corresponding to a[i] in p
            q |= 1L << b[i];     // Set the bit corresponding to b[i] in q
            ans[i] = Long.bitCount(p & q); // Count common set bits (common elements)
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] a1 = {1, 3, 2, 4};
        int[] b1 = {3, 1, 2, 4};
        System.out.println(Arrays.toString(findThePrefixCommonArray(a1, b1))); // Output: [0, 2, 3, 4]

        int[] a2 = {2, 3, 1};
        int[] b2 = {3, 1, 2};
        System.out.println(Arrays.toString(findThePrefixCommonArray(a2, b2))); // Output: [0, 1, 3]
    }
}

Method 1

Enjoy Reading This Article?