Skip to main content

LeetCode 2657 | Find the Prefix Common Array of Two Arrays | Easy Understanding and Code

In this post, we will break down LeetCode problem 2657: Find the Prefix Common Array of Two Arrays step by step. Whether you're new to coding or a seasoned problem-solver, I'll guide you through all possible approaches, from the brute force method to an optimized solution. By the end, you'll understand the problem thoroughly and know the best way to solve it efficiently.

Problem Description

You are given two 0-indexed integer permutations, A and B, of length n. A permutation means that both arrays contain all integers from 1 to n exactly once.

The task is to return the prefix common array C such that:

  • C[i] is the count of numbers that are present at or before index i in both arrays A and B.

Examples

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 in A and B. Hence, C[0] = 0.

  • At i = 1, the common numbers are 1 and 3. Thus, C[1] = 2.

  • At i = 2, 1, 2, and 3 are common. So, C[2] = 3.

  • At i = 3, all numbers (1, 2, 3, 4) are common, making C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]

Constraints:

  • 1 ≤ A.length == B.length == n ≤ 50

  • 1 ≤ A[i], B[i] ≤ n


Approach 1: Brute Force

Steps:

  1. For every index i in A and B:

    • Traverse all elements from 0 to i in both arrays.

    • Count how many numbers are common between the two prefixes.

  2. Append this count to the result array C.

Code Implementation:

class Solution
{
    public:
        vector<int> findThePrefixCommonArray(vector<int> &A, vector<int> &B)
        {
            int n = A.size();
            vector<int> C(n, 0);

            for (int i = 0; i < n; ++i)
            {
                unordered_set<int> seen;
                int count = 0;

                for (int j = 0; j <= i; ++j)
                {
                    seen.insert(A[j]);
                }

                for (int j = 0; j <= i; ++j)
                {
                    if (seen.find(B[j]) != seen.end())
                    {
                        ++count;
                    }
                }

                C[i] = count;
            }

            return C;
        }
};

Complexity Analysis:

  • Time Complexity: O(n^2)

    • For each index i, we loop up to i, leading to a quadratic runtime.

  • Space Complexity: O(n)

    • The unordered_set uses space proportional to the size of the prefix.


Approach 2: Using Two Hash Maps

Instead of recalculating the common elements for each prefix, we maintain two hash maps:

  • One for A to track the count of each element up to the current index.

  • One for B for the same purpose.

Steps:

  1. Traverse the arrays, updating the hash maps for each element at index i.

  2. Count common elements by comparing the keys in both hash maps.

Code Implementation:

class Solution
{
    public:
        vector<int> findThePrefixCommonArray(vector<int> &A, vector<int> &B)
        {
            unordered_map<int, int> mpa, mpb;
            vector<int> C;
            int n = A.size();

            for (int i = 0; i < n; ++i)
            {
                mpa[A[i]]++;
                mpb[B[i]]++;

                int count = 0;
                for (auto &pair : mpa)
                {
                    if (mpb.find(pair.first) != mpb.end())
                    {
                        ++count;
                    }
                }

                C.push_back(count);
            }

            return C;
        }
};

Complexity Analysis:

  • Time Complexity: O(n^2)

    • For each index, we compare keys in the hash maps.

  • Space Complexity: O(n)

    • Two hash maps store up to n elements.


Approach 3: Optimized Solution Using One Array

We can track how many times each number has appeared in both arrays using a single frequency array v.

  • Increment the frequency when a number appears in A or B.

  • If the frequency of a number becomes 2, it means it is common in both arrays.

Steps:

  1. Initialize a frequency array v of size n+1 with all values set to 0.

  2. Traverse both arrays simultaneously.

  3. Update the frequency for each number in A and B.

  4. Increment a count variable when a number becomes common.

  5. Store the count in the result array C.

Code Implementation:

class Solution
{
    public:
        vector<int> findThePrefixCommonArray(vector<int> &A, vector<int> &B)
        {
            int n = A.size();
            vector<int> C(n, 0);
            vector<int> v(n + 1, 0);
            int count = 0;

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

                v[B[i]]++;
                if (v[B[i]] == 2)
                {
                    ++count;
                }

                C[i] = count;
            }

            return C;
        }
};

Complexity Analysis:

  • Time Complexity: O(n)

    • We traverse the arrays once.

  • Space Complexity: O(n)

    • The frequency array v uses O(n) space.


All Approaches Time Complexity

  1. Brute Force: Simple but inefficient with O(n^2) time complexity.

  2. Two Hash Maps: Improves clarity but still O(n^2) time complexity.

  3. Optimized Single Array: Most efficient with O(n) time complexity and O(n) space.

When solving competitive programming problems, always aim for the most optimized solution that meets the constraints. The third approach is the clear winner here, making it the best choice for this problem.


Some Tags:-

  • LeetCode 2657 solution
  • Prefix Common Array explanation
  • LeetCode Prefix Common Array problem
  • Find the Prefix Common Array solution
  • Optimized approach for Prefix Common Array
  • Prefix Common Array brute force method
  • LeetCode array problems explained
  • Coding solutions for LeetCode problems
  • Competitive programming array questions
  • C++ solution for LeetCode 2657
  • Prefix Common Array time complexity analysis
  • Programming tutorials for LeetCode
  • Data structure problems in C++

Popular posts from this blog

Maximum Difference Between Even and Odd Frequency | LeetCode

We are given a string consisting of lowercase English letters. Our task is to find the maximum difference between the frequency of two characters in the string such that: One of the characters has an even frequency . The other character has an odd frequency . The difference is calculated as:  odd_frequency - even_frequency We need to return the maximum possible difference between the odd and even frequencies. Example Walkthrough Let's take a couple of examples to better understand the problem: Example 1: Input:  s = "aaaaabbc" Frequencies: 'a' → 5 (odd) 'b' → 2 (even) 'c' → 1 (odd) Here, the maximum odd frequency is 5 (for 'a') and the maximum even frequency is 2 (for 'b'). Therefore, the result is: maxOdd - maxEven = 5 - 2 = 3 Example 2: Input:  s = "abcabcab" Frequencies: 'a' → 3 (odd) 'b' → 2 (even) 'c' → 2 (even) The maximum odd frequency is 3 (for 'a') and the maximum even fr...
Read more

Top 10 Beginner-Friendly LeetCode Questions and Their Solutions

If you're new to solving coding problems on LeetCode, it can feel overwhelming. Where do you start? Which problems are suitable for beginners? Don’t worry! In this blog post, I’ll guide you through   10 beginner-friendly LeetCode questions   that are perfect for getting started on your coding journey. These problems will help you build confidence, improve your problem-solving skills, and lay a solid foundation in data structures and algorithms. Why Start with Beginner-Friendly Problems? Before diving into advanced topics like dynamic programming or graph theory, it’s essential to: Build a strong foundation in basic programming concepts. Understand how to approach a coding problem methodically. Gain familiarity with LeetCode’s platform and its problem structure. The following problems are simple yet impactful, designed to introduce you to common techniques like loops, arrays, strings, and basic math operations. 10 Beginner-Friendly LeetCode Problems 1.  Two Sum (Easy) Prob...
Read more

Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution. Problem Explanation You are given a string initialCurrency (the starting currency), along with four arrays: pairs1 and rates1 : Represent exchange rates between currency pairs on Day 1. pairs2 and rates2 : Represent exchange rates between currency pairs on Day 2. The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates. Key Insights: Conversion rates are valid (no contradictions). Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2....
Read more