LeetCode 2657 - Find the Prefix Common Array of Two Arrays

In this article, we will solve LeetCode 2657 - Find the Prefix Common Array of Two Arrays using:

• Brute Force Approach
• Optimal Frequency Array Approach

We will also understand:

• Problem intuition
• Dry run
• Time complexity
• Interview explanation

---

🎥 Watch Full Video Explanation

---

📌 Problem Statement

You are given two integer arrays A and B of length n.

A prefix common array C is defined as:

C[i] = number of common elements in:
A[0...i] and B[0...i]
    

✅ Example

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

Output:
[0,2,3,4]
    

Explanation

i	Prefix A	Prefix B	Common Elements	C[i]
0	[1]	[3]	{ }	0
1	[1,3]	[3,1]	{1,3}	2
2	[1,3,2]	[3,1,2]	{1,2,3}	3
3	[1,3,2,4]	[3,1,2,4]	{1,2,3,4}	4

---

🚀 Approach 1: Brute Force

Idea

For every index i, compare every element from:

• A[0...i]
• B[0...i]

If elements are equal, increase the count.

Brute Force Java Code

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++) {

            int count = 0;

            for (int j = 0; j <= i; j++) {

                for (int k = 0; k <= i; k++) {

                    if (A[j] == B[k]) {
                        count++;
                    }
                }
            }

            C[i] = count;
        }

        return C;
    }
}

⏱ Time Complexity

O(n³)
    

Because:

• Outer loop runs n times
• Two nested loops compare prefixes

❌ Why Brute Force is Bad?

• Too many repeated comparisons
• Slow for large inputs
• Not ideal for interviews

---

⚡ Approach 2: Optimal Frequency Array

Key Observation

A number becomes common only when:

• It appears once in A
• And once in B

That means:

frequency becomes 2
    

Optimal Java Code

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {

        int n = A.length;

        int[] result = new int[n];
        int[] freq = new int[n + 1];

        int common = 0;

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

            freq[A[i]]++;

            if (freq[A[i]] == 2) {
                common++;
            }

            freq[B[i]]++;

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

            result[i] = common;
        }

        return result;
    }
}

---

🔍 Dry Run

A = [1,3,2]
B = [3,1,2]
    

i = 0

freq[1] = 1
freq[3] = 1

common = 0
    

i = 1

freq[3] = 2 → common = 1
freq[1] = 2 → common = 2
    

i = 2

freq[2] = 2 → common = 3
    

Final Output

[0,2,3]
    

---

⏱ Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force	O(n³)	O(1)
Optimal Frequency Array	O(n)	O(n)

---

🎯 Interview Tip

The most important observation is:

A number becomes common exactly when it appears in both arrays.

So instead of repeatedly checking prefixes, we track frequencies efficiently.

---

✅ Final Thoughts

This problem is a great example of:

• Prefix processing
• Frequency counting
• Optimization from brute force to linear time

The optimal approach is clean, interview-friendly, and extremely efficient.