2657. Find the Prefix Common Array of Two Arrays

Array
Hash Table
Counting

TIME

O(n)

SPACE

O(n)

Intuition

At each index, one value from A and one value from B become available in the prefixes.

Because both arrays are permutations of 1 to n, a value becomes common exactly when we have seen it twice in total: once from A and once from B.

Approach

Keep a count array seen of size n + 1.
Keep a running common count.
For each index i:
- increment seen[A[i]]; if it becomes 2, increment common
- increment seen[B[i]]; if it becomes 2, increment common
- store common in the answer
Return the answer array.

Complexity

Time: O(n)
Space: O(n)

Edge Cases

A[i] == B[i] -> the value is counted as common at the same index
No common value in early prefixes -> answer contains 0
Last index always reaches n because both arrays are permutations
Single element arrays -> return [1]

Code

from typing import List


class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        """
        2657. Find the Prefix Common Array of Two Arrays
        Time: O(n)
        Space: O(n)
        """
        n = len(A)
        seen = [0] * (n + 1)
        answer = []
        common = 0

        for a, b in zip(A, B):
            seen[a] += 1
            if seen[a] == 2:
                common += 1

            seen[b] += 1
            if seen[b] == 2:
                common += 1

            answer.append(common)

        return answer

/**
 * 2657. Find the Prefix Common Array of Two Arrays
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] seen = new int[n + 1];
        int[] answer = new int[n];
        int common = 0;

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

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

            answer[i] = common;
        }

        return answer;
    }
}