Find the Prefix Common Array of Two Arrays | 3 Detailed Approach | Leetcode 2657 | codestorywithMIK

Hi Everyone, this is the 135th video of our Playlist "Arrays 1D/2D : Popular Interview Problems".
Now we will be solving a good practice problem based on Array - Find the Prefix Common Array of Two Arrays | 3 Approaches | Brute Force | Better | Optimal | Leetcode 2657 | codestorywithMIK
I will also code all the 3 approaches in Java , hence the video might be lengthy, but I really hope it helps you all.

Problem Name : Find the Prefix Common Array of Two Arrays | 3 Approaches | Brute Force | Better | Optimal | Leetcode 2657 | codestorywithMIK
Company Tags : will update later

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Video Summary :
Approach 1 (Brute Force):
The brute force approach iterates over each prefix of the arrays A and B and checks if elements in A are present in B up to the current index. This involves nested loops, leading to a time complexity of O(n3). The idea is straightforward but inefficient due to repeated comparisons.

Approach 2 (Better Approach):
This approach uses two boolean arrays to track which numbers have appeared in A and B up to the current index. For each prefix, it checks all numbers to count common elements. While still checking all numbers for each prefix, the use of auxiliary arrays reduces the complexity to O(n2).

Approach 3 (Optimal Approach):
The optimal approach leverages a hash map to track the frequency of elements from both arrays. When an element's frequency reaches 2, it indicates it is common in the prefix. This approach avoids redundant checks and achieves a linear time complexity of O(n), making it the most efficient solution.

✨ Timelines✨
00:00 - Introduction
00:31 - Motivation
01:31 - Problem Explanation
05:01 - Brute Force O(n^3)
11:13 - Better Approach O(n^2)
19:38 - Best Approach O(n)
29:15 - Coding Approach-1 in Cpp
31:34 - Coding Approach-2 in Cpp
33:46 - Coding Approach-3 in Cpp
34:53 - Coding Approach-1 in JAVA
35:59 - Coding Approach-2 in JAVA
37:14 - Coding Approach-3 in JAVA

#MIK #mik #Mik
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[the_ritesh_patel]

Tomorrow's quotes from my side: “Every single day you waste wishing things were easier, someone else is grinding to take what you’re dreaming of. Success doesn’t wait for anyone. Either you step up now, or you’ll be left behind forever.”

[NandakishorGudala]

Great explanation!!, solved after watching 8 min.

[randomly-unique]

Thank you MIK and Congratulations 🎊 it's 80k strong community now!

[surajbodke]

How about this solution class Solution {
public:
vector<int> A, vector<int>& B) {
int n = A.size();
set<int> seen;
vector<int> rs(n, 0);
int commonCount = 0;

for (int i = 0; i < n; i++) {
commonCount=commonCount+2;
seen.insert(A[i]);
seen.insert(B[i]);
rs[i] = commonCount-seen.size();
}
return rs;
}
};

[annagarg]

Bhaiya, I Solved it with O(50) space complexity and O(50)time complexity Only Because of You ❤, Thankyou so much for all the efforts you are making for us.

[Hpktube]

class Solution {
public:
vector<int> a, vector<int>& b) {
int n = a.size();
vector<int> c(n, 0), freq(52, 0);
for(int i = 0; i<n; i++){
freq[a[i]]++;
freq[b[i]]++;
c[i] = count(freq.begin(), freq.end(), 2);
}
return c;
}
};

[crazygamerrohan]

Kindly Discuss BIt Manipulation Solution

[Krishnesh_Tiwari]

कर्मण्येवाधिकारस्ते मा फलेषु कदाचन।
मा कर्मफलहेतुर्भूर्मा ते सङ्गोऽस्त्वकर्मणि॥ Tomorrow's quotes from my side -- motivation in sanskrit 🥰🥰🥰

[bhupendrakalal]

ooo i didnt realise i too have did it in optimal approach 🥳🥳🥳

[AryanVats]

Esy one today also❤ thanks sir for your teachings

[salmaniproductions]

Thank you so much bhaiyya.. I tried to solve by own but bhot jagah phasss rha tha then aapke paas aya..
My 2 obervation in this problem was -
1. res[0] will always be either 0 or 1
2. res[n-1] will always = n
Even though ye observation kuch kaam nahi aaye question solve krne me but ye ek mind me tha bs...
Thank you bhaiyya.

[eprithvikushwah]

class Solution {
public:
vector<int> A, vector<int>& B) {
int n = A.size();
vector<int> v1(n+1, -1);
vector<int> ans;

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

int cnt = 0;
for(int i = 0; i < n+1; i++ ){
if(v1[i]==1)cnt++;
}
ans.push_back(cnt);
}
return ans;
}
};

[AradhyaVerma-pm]

/*APPROACH-1, WE TOOK 2 BOOLEAN ARRAYS, FOR EACH INDEX
1) mark A[i]= true mark B[i]=true;
2) now from the starting check if both
boolean arrays are marked true;
-> if yes, increase the count
-> if no, eat five star
*/
class Solution2 {
public int[] A, int[] B) {
int n= A.length;
boolean isPresentA[]= new boolean[n+1];
boolean isPresentB[]= new boolean[n+1];
int C[]= new int[n];
for(int i=0;i<n;i++){
int a= A[i]; int b= B[i];
isPresentA[a]=true;
isPresentB[b]=true;
int count=0;
for(int j=1;j<=n;j++){
if(isPresentA[j]== true && isPresentB[j]==true)
count++;
}
C[i]=count;
}
return C;
}
}

/*APPROACH -2 We Somehow figured out, that every element
occures at most twice, therefore:
1) We used a freq array, and incremented frequency of each
character of A[i] and B[i] by one
2) by using a supplementary function, we found all of the frequencies
which are updated upto 2
we store the result in C[i]
*/
class Solution1 {
public int countFreq(int freq[]){
int n= freq.length; int count=0;
for(int i=0;i<n;i++){
if(freq[i]==2)
count++;
}
return count;
}
public int[] A, int[] B) {
int count=0;
int n= A.length;
int C[]= new int[n];
int freq[]= new int[n+1];
for(int i=0;i<n;i++){
int a= A[i], b= B[i];
freq[a]++; freq[b]++;
C[i]= countFreq(freq);
}
return C;
}
}

/*Approach-3 Since we figured it out that, all the elements occur
atmost twice, then there is no use of an external function
1) use a hashmap instead: and increment frequency by 1
2) when frequency reached 2 : we inrement the counter
*/
class Solution3 {
public int[] A, int[] B) {
int count=0;
int n= A.length;
int result[]= new int[n];
HashMap<Integer, Integer> map= new HashMap<>();
for(int i=0;i<n;i++){
map.put(A[i], map.getOrDefault(A[i], 0)+1);
if(map.get(A[i])==2) count++;
map.put(B[i], map.getOrDefault(B[i], 0)+1);
if(map.get(B[i])==2) count++;
result[i]=count;
}
return result;
}
}
//BETTER ALTERNATIVE
class Solution {
public int[] A, int[] B) {
int n=A.length;
int[] freq=new int[n+1];
int[] result=new int[n];
int count=0;
for(int i=0;i<n;i++)
{
if(++freq[A[i]]==2)
count++;
if(++freq[B[i]]==2)
count++;
result[i]=count;
}
return result;
}
}

[vinaymaurya]

I solved it myself using unordered set, my approach:
class Solution {
public:
vector<int> A, vector<int>& B) {
int n = A.size();
unordered_set<int> visited;
unordered_set<int> seen;
vector<int> result(n, 0);
for (int i = 0; i < n; i++) {
if (seen.count(A[i]))
visited.insert(A[i]);
else
seen.insert(A[i]);
if (seen.count(B[i]))
visited.insert(B[i]);
else
seen.insert(B[i]);
result[i] = visited.size();
}
return result;
}
};

[atishayjain]

I have done it with the help of a single unordered set and with a time complexity of O(n) .Here's my code:-
class Solution {
public:
vector<int> A, vector<int>& B) {
unordered_set<int> mp;
vector<int> res;
int cnt=0;
for(int i=0;i<A.size();i++)
{
if(mp.find(A[i])!=mp.end())
{
cnt++;
}
else mp.insert(A[i]);
if(mp.find(B[i])!=mp.end())
{
cnt++;
}
else mp.insert(B[i]);
res.push_back(cnt);
}
return res;
}
};

[SatyamSingh-xqzk]

I did it in O(n²) TC, without seeing soln and code, kudos to you MIK sir👏

[vishwashsoni]

sir this is how i solved this question :

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

if(A[0] == B[0]){
st.insert(A[0]);
ans[0] = 1;
}
else{
st.insert(A[0]);
st.insert(B[0]);
}
for(int i=1;i<n;i++){
if(A[i] == B[i]){
st.insert(A[i]);
ans[i] = ans[i-1]+1;
}
else{
if(st.find(A[i])!=st.end() && st.find(B[i])!=st.end()){
ans[i] = ans[i-1]+2;
st.insert(A[i]);
st.insert(B[i]);
}
else if(st.find(A[i])!=st.end() || st.find(B[i])!=st.end()){
ans[i] = ans[i]+ans[i-1]+1;
st.insert(A[i]);
st.insert(B[i]);
}
else{
ans[i] = ans[i-1];
st.insert(A[i]);
st.insert(B[i]);
}
}
}
return ans;
}
};

[worldofgaming]

Tomorrow's quotes from my side:""Motivation may fade, but discipline and obsession are the fuel that never run dry.""

[adityazende]

For O(n) solution the most important word is "permutation".

[dayashankarlakhotia]

public int[]findThePrefixCommonArray(A[], B[]){
int n=A.length, cnt=0;
int[]ans=new int[n];
int[]frq=new int[n+1];
for(int i=0;i<n;i++){
if(++freq[A[i]]==2) cnt++;
if(++freq[B[i]==2)
cnt++;
ans[i]=cnt;
}
return ans;
}🎉❤