Find the Prefix Common Array of Two Arrays

MEDIUM

Description

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.

Constraints:

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

Approaches

Checkout 3 different approaches to solve Find the Prefix Common Array of Two Arrays. Click on different approaches to view the approach and algorithm in detail.

Brute Force using Sets for Each Prefix

This approach directly follows the problem definition. We iterate through each possible prefix length, from 1 to n. For each length i+1, we consider the subarrays A[0...i] and B[0...i]. We convert these two subarrays into sets to easily find their common elements. The size of the intersection of these two sets gives us the value for C[i].

Algorithm

Initialize an integer array C of size n.
Loop with an index i from 0 to n-1.
Inside the loop, create two hash sets, setA and setB.
Populate setA with elements from A[0...i].
Populate setB with elements from B[0...i].
Initialize a counter commonCount to 0.
Iterate through the elements of setA. For each element, check if it is present in setB.
If an element is found in both sets, increment commonCount.
After checking all elements, assign C[i] = commonCount.
After the loop finishes, return the array C.

This method is straightforward but computationally expensive. For every index i, it constructs the prefixes of A and B from scratch, converts them to sets, and then computes the intersection size. This leads to a quadratic time complexity because the work done at each step i is proportional to i, and this is repeated for all n steps.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] C = new int[n];

        for (int i = 0; i < n; i++) {
            Set<Integer> setA = new HashSet<>();
            for (int j = 0; j <= i; j++) {
                setA.add(A[j]);
            }

            Set<Integer> setB = new HashSet<>();
            for (int j = 0; j <= i; j++) {
                setB.add(B[j]);
            }

            int commonCount = 0;
            for (int num : setA) {
                if (setB.contains(num)) {
                    commonCount++;
                }
            }
            C[i] = commonCount;
        }
        return C;
    }
}

Complexity Analysis

Time Complexity: O(n^2). The outer loop runs `n` times. Inside the loop, we build two sets of size `i+1` and then iterate through one to find the intersection. This takes O(i) time. The total time is the sum of O(i) for `i` from 0 to `n-1`, which is O(n^2).Space Complexity: O(n). At each step `i`, we create two sets that can grow up to size `n`. The space required is proportional to the largest prefix, which is `n`.

Pros and Cons

Pros:

Simple to understand and implement, as it directly translates the problem statement.

Cons:

Inefficient due to redundant computations. For each i, it re-scans and re-processes all elements in the prefixes up to i.

Code Solutions

Checking out 3 solutions in different languages for Find the Prefix Common Array of Two Arrays. Click on different languages to view the code.

class Solution {
public
  int[] findThePrefixCommonArray(int[] A, int[] B) {
    int n = A.length;
    int[] ans = new int[n];
    int[] cnt1 = new int[n + 1];
    int[] cnt2 = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      ++cnt1[A[i]];
      ++cnt2[B[i]];
      for (int j = 1; j <= n; ++j) {
        ans[i] += Math.min(cnt1[j], cnt2[j]);
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Find the Prefix Common Array of Two Arrays

Patterns:

Bit Manipulation

Data Structures:

ArrayHash Table