LeetCode - Find the Prefix Common Array of Two Arrays

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays

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.

Explanation

Brute Force

We need to return an array result of the same length such that result[i] is the number of elements that are common in both A and B. We can start by creating two hash maps map1 and m2 to store the indices of each element in A and B, respectively.

We then iterate over array A and count the number of elements that are common to both A and B up to that point. We do this by checking if the index of each element in A is less than or equal to i and the index of the same element in B is also less than or equal to i. We store the count in an array result and return it as the answer.

A C++ snippet of the above approach is as follows:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
    int n = A.size();
    unordered_map<int, int> map1, map2;

    for(int i = 0; i < n; i++) {
        map1[A[i]] = i;
        map2[B[i]] = i;
    }

    vector<int> result(n);

    for(int i = 0; i < n; i++) {
        int count = 0;

        for(int j = 0; j <= i; j++) {
            if(m1[A[j]] <= i && m2[A[j]] <= i) {
                count++;
            }
        }

        result[i] = count;
    }

    return result;
}

The time complexity of this solution is O(n^2), since we are using two nested for loops. The space complexity is O(n).

Efficient solution

To find the prefix common array, we can iterate over arrays A and B simultaneously and keep track of the frequency of each integer in both arrays using an array seen. For each element in A and B, we increment the corresponding element in seen and check if its frequency becomes 2. If the frequency becomes 2, it means that the element is present in both A and B at or before the current index i.

We update the corresponding element in the result array result by adding 1 if the frequency of the element in A or B becomes 2, otherwise we add 0.

Finally, we compute the prefix sum of the result array to get the prefix common array of A and B.

Let's check the algorithm to understand it clearly.

Algorithm

- set current = 0
      n = A.size()

- set result(n)
      seen(n + 1)

- loop for i = 0; i < n; i++
  - seen[A[i]] = seen[A[i]] + 1
  - if seen[A[i]] == 2
    - current++
  - if end

  - seen[B[i]] = seen[B[i]] + 1
  - if seen[B[i]] == 2
    - current++
  - if end

  - result[i] = current
- for end

- return result

The time complexity of this approach is O(n). The space complexity of this approach is O(n).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int current = 0, n = A.size();
        vector<int> result(n), seen(n + 1);

        for (int i = 0; i < n; ++i) {
            if (++seen[A[i]] == 2) {
                current++;
            }

            if (++seen[B[i]] == 2) {
                current++;
            }

            result[i] = current;
        }
        return result;
    }
};

Golang solution

func findThePrefixCommonArray(A []int, B []int) []int {
    current, n := 0, len(A)
    result, seen := make([]int, n), make([]int, n + 1)

    for i := 0; i < n; i++ {
        seen[A[i]]++
        if seen[A[i]] == 2 {
            current++
        }

        seen[B[i]]++
        if seen[B[i]] == 2 {
            current++
        }

        result[i] = current
    }

    return result
}

JavaScript solution

var findThePrefixCommonArray = function(A, B) {
    let current = 0, n = A.length;
    let result = new Array(n), seen = new Array(n + 1).fill(0);

    for (let i = 0; i < n; ++i) {
        if (++seen[A[i]] == 2) {
            current++;
        }

        if (++seen[B[i]] == 2) {
            current++;
        }

        result[i] = current;
    }

    return result;
};

Let's dry-run our algorithm for a few examples to see how the solution works.

Input: A = [1, 3, 2, 4]
       B = [3, 1, 2, 4]

Step 1: int current = 0, n = A.size();
        vector<int> result(n), seen(n + 1);

Step 2: loop for i = 0; i < n;
          0 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[0]
                 = 1

            seen[A[i]] = seen[A[0]]
                       = seen[1]
                       = 0

            ++seen[A[i]] = 1

            1 == 2
            false

            seen = [0, 1, 0, 0, 0]

          if ++seen[B[i]] == 2
            B[i] = B[0]
                 = 3

            seen[B[i]] = seen[B[0]]
                       = seen[3]
                       = 0

            ++seen[B[i]] = 1

            1 == 2
            false

            seen = [0, 1, 0, 1, 0]

          result[i] = current
          result[0] = 0
          result = [0, 0, 0, 0]

          i++
          i = 1

Step 3: for i < n
          1 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[1]
                 = 3

            seen[A[i]] = seen[A[1]]
                       = seen[3]
                       = 1

            ++seen[A[i]] = 2

            2 == 2
            true
            current++
            current = 1

            seen = [0, 1, 0, 2, 0]

          if ++seen[B[i]] == 2
            B[i] = B[1]
                 = 1

            seen[B[i]] = seen[B[0]]
                       = seen[1]
                       = 1

            ++seen[B[i]] = 2

            2 == 2
            true

            current++
            current = 2

            seen = [0, 2, 0, 2, 0]

          result[i] = current
          result[1] = 2
          result = [0, 2, 0, 0]

          i++
          i = 2

Step 4: for i < n
          2 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[2]
                 = 2

            seen[A[i]] = seen[A[2]]
                       = seen[2]
                       = 0

            ++seen[A[i]] = 1

            1 == 2
            false

            seen = [0, 2, 1, 2, 0]

          if ++seen[B[i]] == 2
            B[i] = B[2]
                 = 2

            seen[B[i]] = seen[B[2]]
                       = seen[2]
                       = 1

            ++seen[B[i]] = 2

            2 == 2
            true

            current++
            current = 3

            seen = [0, 2, 2, 2, 0]

          result[i] = current
          result[2] = 3
          result = [0, 2, 3, 0]

          i++
          i = 3

Step 5: for i < n
          3 < 4
          true

          if ++seen[A[i]] == 2
            A[i] = A[3]
                 = 4

            seen[A[i]] = seen[A[2]]
                       = seen[4]
                       = 0

            ++seen[A[i]] = 1

            1 == 2
            false

            seen = [0, 2, 2, 2, 1]

          if ++seen[B[i]] == 2
            B[i] = B[3]
                 = 4

            seen[B[i]] = seen[B[3]]
                       = seen[4]
                       = 1

            ++seen[B[i]] = 2

            2 == 2
            true

            current++
            current = 4

            seen = [0, 2, 2, 2, 2]

          result[i] = current
          result[3] = 4
          result = [0, 2, 3, 4]

          i++
          i = 4

Step 6: for i < n
          4 < 4
          false

Step 7: return result

We return the result as [0, 2, 3, 4].

Did you find this article valuable?

Support Alkesh Ghorpade's Blog by becoming a sponsor. Any amount is appreciated!