2657. Prefix Common Array of Two Arrays Solution

Q: Is Find the Prefix Common Array of Two Arrays easy or hard?

The problem is rated Medium because the core logic is simple but requires recognizing the prefix property and using an efficient tracking structure. Once you realize that a value becomes common when seen twice, the O(n) implementation becomes straightforward.

Q: Find the Prefix Common Array of Two Arrays Python/Java solution

In Python or Java, iterate once through the arrays while updating a frequency array or hash sets. Increment a counter whenever an element appears in both prefixes. Store the counter at each step to build the prefix common array in O(n) time.

Q: How to solve Find the Prefix Common Array of Two Arrays in O(n)?

Iterate through both arrays simultaneously. Maintain a frequency array or hash structure to record seen elements. Whenever an element's count reaches two (meaning it appeared in both prefixes), increment a running counter and store it in the result for that index.

Q: What is the best approach for Find the Prefix Common Array of Two Arrays?

The most efficient approach uses a single presence-count array. Because both arrays are permutations of 1..n, you can track occurrences with a frequency array and increment the common counter when a value appears for the second time. This runs in O(n) time with O(n) space and avoids hash table overhead.

Q: Is Find the Prefix Common Array of Two Arrays asked at Google/Amazon/Meta?

Prefix counting and hash-based tracking problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve tracking shared elements across prefixes or streams are common in array and hash table interview rounds.

Q: What data structure is used in Find the Prefix Common Array of Two Arrays?

Typical solutions use either hash sets or a frequency array. Hash sets allow O(1) membership checks, while a counting array works even faster when the value range is known, such as the 1..n permutation constraint in this problem.

Q: What is the time complexity of Find the Prefix Common Array of Two Arrays?

The optimal solution runs in O(n) time because each index is processed exactly once. Each step performs constant-time updates to either hash sets or a counting array. Space complexity is O(n) due to the additional data structure used to track seen elements.

The problem

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.

Approach overview

Problem Overview: You are given two arrays A and B, both permutations of numbers from 1..n. For each index i, compute how many values appear in both prefixes A[0..i] and B[0..i]. The result is the prefix common array where result[i] stores that count.

Approach 1: Using Two Sets to Track Common Elements (Time: O(n), Space: O(n))

This approach maintains two hash sets that store elements seen so far in each prefix. As you iterate index i from 0 to n-1, insert A[i] into the first set and B[i] into the second. After each insertion, check whether the newly added values exist in the opposite set using constant-time hash lookups. Every time a match is found, increment the running count of common elements and store it in the result array. The key insight is that an element becomes "prefix common" exactly when it has appeared in both prefixes. Hash sets make these membership checks O(1), giving an overall O(n) traversal. This approach is easy to reason about and works well whenever fast membership checks are needed using a hash table.

Approach 2: Using a Single Array to Track Presence (Time: O(n), Space: O(n))

Since both arrays are permutations of 1..n, you can replace hash sets with a simple counting array. Maintain an integer array freq of size n + 1. For each index i, increment freq[A[i]] and freq[B[i]]. When a value's count becomes 2, it means the element has appeared in both prefixes, so you increase the common counter. Store the running count in the result. This works because every value appears exactly once in each array, so the second occurrence signals a match. The approach avoids hash structures and uses direct indexing, which is faster in practice. The idea resembles techniques used in array counting problems and sometimes pairs nicely with bit manipulation optimizations when memory is tightly controlled.

Recommended for interviews: The single-array presence approach is typically preferred. It exploits the permutation constraint and produces a clean O(n) solution with minimal overhead. Interviewers often expect you to first reason about tracking seen elements (the two-set idea) and then optimize it by replacing hash structures with an indexed array.

Approach 1: Using Two Sets to Track Common Elements

This approach involves two sets to track elements of A and B as you traverse them. For each index i, you will check how many elements have been seen in both sets. This allows us to efficiently count common elements at each index.

Python

def find_prefix_common_array(A, B):
    seen_a, seen_b = set(), set()
    C = []
    common = 0
    for a, b in zip(A, B):
        seen_a.add(a)
        seen_b.add(b)
        # Increment common if both numbers are in both sets
        if a in seen_b: common += 1
        if b in seen_a and a != b: common += 1
        C.append(common)
    return C

Java

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

public class PrefixCommonArray {
    public int[] findPrefixCommonArray(int[] A, int[] B) {
        Set<Integer> setA = new HashSet<>(), setB = new HashSet<>();
        int[] C = new int[A.length];
        int common = 0;
        for (int i = 0; i < A.length; i++) {
            setA.add(A[i]);
            setB.add(B[i]);
            if (setA.contains(A[i]) && setB.contains(A[i])) common++;
            if (A[i] != B[i] && setA.contains(B[i]) && setB.contains(B[i])) common++;
            C[i] = common;
        }
        return C;
    }
}

C++

#include <vector>
#include <unordered_set>
using namespace std;

vector<int> findPrefixCommonArray(vector<int>& A, vector<int>& B) {
    unordered_set<int> setA, setB;
    vector<int> C(A.size());
    int common = 0;
    for (int i = 0; i < A.size(); i++) {
        int a = A[i];
        int b = B[i];
        setA.insert(a);
        setB.insert(b);
        if (setA.find(a) != setA.end() && setB.find(a) != setB.end()) common++;
        if (a != b && setA.find(b) != setA.end() && setB.find(b) != setB.end()) common++;
        C[i] = common;
    }
    return C;
}

JavaScript

function findPrefixCommonArray(A, B) {
    const seenA = new Set(), seenB = new Set();
    const C = [];
    let common = 0;
    for (let i = 0; i < A.length; i++) {
        seenA.add(A[i]);
        seenB.add(B[i]);
        if (seenA.has(A[i]) && seenB.has(A[i])) common++;
        if (A[i] !== B[i] && seenA.has(B[i]) && seenB.has(B[i])) common++;
        C.push(common);
    }
    return C;
}

#include <stdio.h>
#include <stdbool.h>

int* findPrefixCommonArray(int* A, int* B, int n, int* returnSize) {
    int seenA[51] = {0}, seenB[51] = {0};
    int* C = (int*)malloc(n * sizeof(int));
    int common = 0;
    
    for (int i = 0; i < n; i++) {
        seenA[A[i]] = 1;
        seenB[B[i]] = 1;
        
        if (seenA[A[i]] && seenB[A[i]]) common++;
        if (seenA[B[i]] && seenB[B[i]] && A[i] != B[i]) common++;
        C[i] = common;
    }
    *returnSize = n;
    return C;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[] FindPrefixCommonArray(int[] A, int[] B) {
        HashSet<int> seenA = new HashSet<int>();
        HashSet<int> seenB = new HashSet<int>();
        int[] C = new int[A.Length];
        int common = 0;
        for (int i = 0; i < A.Length; i++) {
            seenA.Add(A[i]);
            seenB.Add(B[i]);
            if (seenA.Contains(A[i]) && seenB.Contains(A[i])) common++;
            if (A[i] != B[i] && seenA.Contains(B[i]) && seenB.Contains(B[i])) common++;
            C[i] = common;
        }
        return C;
    }
}

Using Python sets, the solution adds elements from A and B to 'seen_a' and 'seen_b' respectively, checking whether each element is present in both sets and incrementing the common count as necessary.

Complexity

Time Complexity: O(n), iterating over both lists. Space Complexity: O(n), using distinct set objects.

Try this approach in the editor

Approach 2: Using a Single Array to Track Presence

This approach utilizes a single integer array of length n+1 to track occurrences. As you iterate, you update this array for presence in A and B. The count of elements present in both arrays is updated based on the state of this tracking array.

Python

def find_prefix_common_array(A, B):
    occurrence = [0] * (len(A) + 1)
    C = []
    common = 0
    for a, b in zip(A, B):
        occurrence[a] += 1
        if occurrence[a] == 2:
            common += 1
        occurrence[b] += 1
        if occurrence[b] == 2:
            common += 1
        C.append(common)
    return C

Java

public class PrefixCommonArraySingleArray {
    public int[] findPrefixCommonArray(int[] A, int[] B) {
        int[] occurrence = new int[A.length + 1];
        int[] C = new int[A.length];
        int common = 0;
        for (int i = 0; i < A.length; i++) {
            if (++occurrence[A[i]] == 2) common++;
            if (++occurrence[B[i]] == 2) common++;
            C[i] = common;
        }
        return C;
    }
}

C++

#include <vector>
using namespace std;

vector<int> findPrefixCommonArray(vector<int>& A, vector<int>& B) {
    vector<int> occurrence(A.size() + 1, 0);
    vector<int> C(A.size(), 0);
    int common = 0;
    for (int i = 0; i < A.size(); i++) {
        if (++occurrence[A[i]] == 2) common++;
        if (++occurrence[B[i]] == 2) common++;
        C[i] = common;
    }
    return C;
}

JavaScript

function findPrefixCommonArray(A, B) {
    const occurrence = new Array(A.length + 1).fill(0);
    const C = [];
    let common = 0;
    for (let i = 0; i < A.length; i++) {
        if (++occurrence[A[i]] === 2) common++;
        if (++occurrence[B[i]] === 2) common++;
        C.push(common);
    }
    return C;
}

#include <stdio.h>
#include <stdlib.h>

int* findPrefixCommonArray(int* A, int* B, int n, int* returnSize) {
    int occurrence[51] = {0};
    int* C = (int*)malloc(n * sizeof(int));
    int common = 0;
    
    for (int i = 0; i < n; i++) {
        if (++occurrence[A[i]] == 2) common++;
        if (++occurrence[B[i]] == 2) common++;
        C[i] = common;
    }
    *returnSize = n;
    return C;
}

using System;

public class Solution {
    public int[] FindPrefixCommonArray(int[] A, int[] B) {
        int[] occurrence = new int[A.Length + 1];
        int[] C = new int[A.Length];
        int common = 0;
        for (int i = 0; i < A.Length; i++) {
            if (++occurrence[A[i]] == 2) common++;
            if (++occurrence[B[i]] == 2) common++;
            C[i] = common;
        }
        return C;
    }
}

In Python, an 'occurrence' list is used to track presence. The commonality of numbers from A and B is determined by this list, updating the common count whenever the same number is seen in both.

Complexity

Time Complexity: O(n). Space Complexity: O(n).

Try this approach in the editor

Approach 3: Counting

We can use two arrays cnt1 and cnt2 to record the occurrence times of each element in arrays A and B respectively, and use an array ans to record the answer.

Traverse arrays A and B, increment the occurrence times of A[i] in cnt1, and increment the occurrence times of B[i] in cnt2. Then enumerate j \in [1,n], calculate the minimum occurrence times of each element j in cnt1 and cnt2, and accumulate them into ans[i].

After the traversal, return the answer array ans.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of arrays A and B.

TypeScript

function findThePrefixCommonArray(A: number[], B: number[]): number[] {
    const n = A.length;
    const cnt1: number[] = Array(n + 1).fill(0);
    const cnt2: number[] = Array(n + 1).fill(0);
    const ans: number[] = Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        ++cnt1[A[i]];
        ++cnt2[B[i]];
        for (let j = 1; j <= n; ++j) {
            ans[i] += Math.min(cnt1[j], cnt2[j]);
        }
    }
    return ans;
}

func findThePrefixCommonArray(A []int, B []int) []int {
	n := len(A)
	cnt1 := make([]int, n+1)
	cnt2 := make([]int, n+1)
	ans := make([]int, n)
	for i, a := range A {
		b := B[i]
		cnt1[a]++
		cnt2[b]++
		for j := 1; j <= n; j++ {
			ans[i] += min(cnt1[j], cnt2[j])
		}
	}
	return ans
}

Try this approach in the editor

Approach 4: Bit Operation (XOR Operation)

We can use an array vis of length n+1 to record the occurrence situation of each element in arrays A and B, the initial value of array vis is 1. In addition, we use a variable s to record the current number of common elements.

Next, we traverse arrays A and B, update vis[A[i]] = vis[A[i]] \oplus 1, and update vis[B[i]] = vis[B[i]] \oplus 1, where \oplus represents XOR operation.

If at the current position, the element A[i] has appeared twice (i.e., it has appeared in both arrays A and B), then the value of vis[A[i]] will be 1, and we increment s. Similarly, if the element B[i] has appeared twice, then the value of vis[B[i]] will be 1, and we increment s. Then add the value of s to the answer array ans.

After the traversal, return the answer array ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of arrays A and B.

TypeScript

function findThePrefixCommonArray(A: number[], B: number[]): number[] {
    const n = A.length;
    const vis: number[] = Array(n + 1).fill(1);
    const ans: number[] = [];
    let s = 0;
    for (let i = 0; i < n; ++i) {
        const [a, b] = [A[i], B[i]];
        vis[a] ^= 1;
        s += vis[a];
        vis[b] ^= 1;
        s += vis[b];
        ans.push(s);
    }
    return ans;
}

func findThePrefixCommonArray(A []int, B []int) (ans []int) {
	vis := make([]int, len(A)+1)
	for i := range vis {
		vis[i] = 1
	}
	s := 0
	for i, a := range A {
		b := B[i]
		vis[a] ^= 1
		s += vis[a]
		vis[b] ^= 1
		s += vis[b]
		ans = append(ans, s)
	}
	return
}

Try this approach in the editor

Approach 5: Bit Manipulation (Space Optimization)

Since the elements of arrays A and B are in the range [1, n] and do not exceed 50, we can use an integer x and an integer y to represent the occurrence of each element in arrays A and B, respectively. Specifically, we use the i-th bit of integer x to indicate whether element i has appeared in array A, and the i-th bit of integer y to indicate whether element i has appeared in array B.

The time complexity of this solution is O(n), where n is the length of arrays A and B. The space complexity is O(1).

TypeScript

function findThePrefixCommonArray(A: number[], B: number[]): number[] {
    const n = A.length;
    const ans: number[] = [];
    let [x, y] = [0n, 0n];
    for (let i = 0; i < n; i++) {
        x |= 1n << BigInt(A[i]);
        y |= 1n << BigInt(B[i]);
        ans.push(bitCount64(x & y));
    }
    return ans;
}

function bitCount64(i: bigint): number {
    i = i - ((i >> 1n) & 0x5555555555555555n);
    i = (i & 0x3333333333333333n) + ((i >> 2n) & 0x3333333333333333n);
    i = (i + (i >> 4n)) & 0x0f0f0f0f0f0f0f0fn;
    i = i + (i >> 8n);
    i = i + (i >> 16n);
    i = i + (i >> 32n);
    return Number(i & 0x7fn);
}

func findThePrefixCommonArray(A []int, B []int) []int {
	n := len(A)
	ans := make([]int, n)
	var x, y int
	for i := 0; i < n; i++ {
		x |= 1 << A[i]
		y |= 1 << B[i]
		ans[i] = bits.OnesCount(uint(x & y))
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Two Sets to Track Common Elements	Time Complexity: O(n), iterating over both lists. Space Complexity: O(n), using distinct set objects.
Using a Single Array to Track Presence	Time Complexity: O(n). Space Complexity: O(n).
Counting	–
Bit Operation (XOR Operation)	–
Bit Manipulation (Space Optimization)	–

Complexity analysis

Approach	Time	Space	When to Use
Two Sets to Track Common Elements	O(n)	O(n)	General solution when arrays may not be permutations or when hash-based membership checks are preferred
Single Array Presence Tracking	O(n)	O(n)	Best when values are in range 1..n; avoids hash tables and runs faster in practice

Frequently asked questions

Is Find the Prefix Common Array of Two Arrays easy or hard?

The problem is rated Medium because the core logic is simple but requires recognizing the prefix property and using an efficient tracking structure. Once you realize that a value becomes common when seen twice, the O(n) implementation becomes straightforward.

Find the Prefix Common Array of Two Arrays Python/Java solution

In Python or Java, iterate once through the arrays while updating a frequency array or hash sets. Increment a counter whenever an element appears in both prefixes. Store the counter at each step to build the prefix common array in O(n) time.

How to solve Find the Prefix Common Array of Two Arrays in O(n)?

Iterate through both arrays simultaneously. Maintain a frequency array or hash structure to record seen elements. Whenever an element's count reaches two (meaning it appeared in both prefixes), increment a running counter and store it in the result for that index.

What is the best approach for Find the Prefix Common Array of Two Arrays?

The most efficient approach uses a single presence-count array. Because both arrays are permutations of 1..n, you can track occurrences with a frequency array and increment the common counter when a value appears for the second time. This runs in O(n) time with O(n) space and avoids hash table overhead.

Is Find the Prefix Common Array of Two Arrays asked at Google/Amazon/Meta?

Prefix counting and hash-based tracking problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve tracking shared elements across prefixes or streams are common in array and hash table interview rounds.

What data structure is used in Find the Prefix Common Array of Two Arrays?

Typical solutions use either hash sets or a frequency array. Hash sets allow O(1) membership checks, while a counting array works even faster when the value range is known, such as the 1..n permutation constraint in this problem.

What is the time complexity of Find the Prefix Common Array of Two Arrays?

The optimal solution runs in O(n) time because each index is processed exactly once. Each step performs constant-time updates to either hash sets or a counting array. Space complexity is O(n) due to the additional data structure used to track seen elements.

Find the Prefix Common Array of Two Arrays solution and explanation

The problem

Approach overview

Approach 1: Using Two Sets to Track Common Elements

Approach 2: Using a Single Array to Track Presence

Approach 3: Counting

Approach 4: Bit Operation (XOR Operation)

Approach 5: Bit Manipulation (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Prefix Common Array of Two Arrays solution and explanation

The problem

Approach overview

Approach 1: Using Two Sets to Track Common Elements

Approach 2: Using a Single Array to Track Presence

Approach 3: Counting

Approach 4: Bit Operation (XOR Operation)

Approach 5: Bit Manipulation (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems