By Expert Funda Wednesday, May 20, 2026

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.

Continue Reading →