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

Count Mentions Per User | Leetcode | Problem Explanation and Solution Approaches

Tracking mentions in messages is a common task in communication-based applications. This blog post breaks down a complex problem, "Count Mentions Per User," and walks through how to solve it efficiently with a clear understanding of all rules and constraints. Problem Statement You are given: An integer numberOfUsers representing the total number of users. An array events where each element is of size n x 3 and describes either a "MESSAGE" or an "OFFLINE" event. Each event can be one of the following types: MESSAGE Event : ["MESSAGE", "timestamp", "mentions_string"] Indicates that users are mentioned in a message at a specific timestamp. The mentions_string can contain: id<number> : Mentions a specific user (e.g., id0 , id1 ). ALL : Mentions all users (online or offline). HERE : Mentions only users who are online at the time. OFFLINE Event : ["OFFLINE", "timestamp", "id<number>"] In...
Read more