Introduction

LeetCode 2657 – Find the Prefix Common Array of Two Arrays is an interesting prefix and hashing problem that tests your understanding of:

1. Prefix processing
2. Hashing
3. Frequency counting
4. Set operations
5. Array traversal

At first glance, the problem may look confusing because of the term:

But once you understand the meaning of prefixes and common elements, the problem becomes straightforward.

This problem is useful for improving:

1. Prefix-based thinking
2. Hashing intuition
3. Optimization skills
4. Interview problem-solving ability

Problem Link

🔗 Find the prefix Common Array of Two Arrays

Problem Statement

You are given two permutations:

Both arrays contain numbers:

exactly once.

You need to create an array:

where:

represents:

Count of numbers present in both arrays from index 0 to i.

Understanding Prefix Common Array

Suppose:

Prefix at Index 0

Common numbers:

So:

Prefix at Index 1

Common numbers:

So:

Final Output

Key Observation

Both arrays are permutations.

This means:

1. Every number appears exactly once.
2. Once a number appears in both prefixes, it remains common forever.

This simplifies the logic significantly.

Brute Force Approach

Intuition

For every index:

1. Build prefixes
2. Compare elements
3. Count common numbers

Brute Force Algorithm

For each index:

1. Traverse all previous elements
2. Check whether numbers exist in both prefixes
3. Count matches

Brute Force Complexity

Time Complexity

because for every index we may scan previous elements.

Space Complexity

Understanding Approach

This approach uses:

1. HashMap
2. Prefix tracking
3. Counting common values

The idea is:

1. Store prefix elements from B
2. Traverse A prefix
3. Count matching numbers

This works because prefixes gradually expand.

Java Solution

Better Optimized Approach

We can solve this more cleanly using:

or frequency counting.

Optimized Intuition

At every index:

1. Add A[i]
2. Add B[i]
3. Track which numbers appeared
4. If a number appears in both arrays, increase common count

Best Optimized Approach Using Frequency Array

Because values are from:

we can use a frequency array.

Optimized Java Solution

Why Does This Work?

Every number appears once in A and once in B.

So:

1. First appearance → frequency becomes 1
2. Second appearance → frequency becomes 2

When frequency becomes:

it means the number has appeared in both prefixes.

So we increase:

Dry Run

Input

Step 1

Index:

Add:

Frequencies:

No common elements.

Step 2

Add:

Frequencies:

Two common elements found.

Step 3

Add:

Frequency:

Common becomes:

Step 4

Add:

Frequency:

Common becomes:

Final Output

Time Complexity Analysis

Time Complexity

Nested traversal inside loop.

Space Complexity

Optimized Frequency Approach

Time Complexity

Single traversal.

Space Complexity

Frequency array.

HashMap vs Frequency Array

Interview Explanation

In interviews, explain:

Since both arrays are permutations, every number appears exactly twice overall — once in A and once in B. Using frequency counting, whenever a number’s frequency becomes 2, it means it has appeared in both prefixes.

This demonstrates:

1. Prefix understanding
2. Optimization thinking
3. Hashing skills

Common Mistakes

1. Recalculating Common Elements Every Time

This causes:

complexity.

2. Forgetting Arrays Are Permutations

This special condition allows frequency optimization.

3. Incorrect Prefix Logic

Remember:

FAQs

Q1. Why is this called Prefix Common Array?

Because:

stores common elements between prefixes ending at index:

Q2. Why does frequency 2 mean common?

Because every number appears once in each array.

Q3. Which approach is best?

Frequency array approach is the most optimized.

Q4. Is this problem important for interviews?

Yes.

It tests:

1. Prefix logic
2. Hashing
3. Optimization
4. Array traversal

Related Problems

After mastering this problem, practice:

1. Intersection of Two Arrays
2. Intersection of Two Arrays II
3. Contains Duplicate
4. Subarray Sum Equals K
5. Prefix Sum
6. Find the Difference of Two Arrays

Conclusion

LeetCode 2657 is an excellent prefix and hashing problem.

It teaches:

1. Prefix processing
2. Frequency counting
3. Optimization techniques
4. Hashing fundamentals

The key insight is:

A number becomes common exactly when its frequency becomes 2.

Once you understand this observation, the optimized solution becomes very simple and efficient.