Find common elements in 3 sorted arrays | Q19 | Love Babbar DSA Sheet | leetcode | Best Approach

#competitiveprogramming #dsasheet #interviewpreparation

In this video I have solved the 19th problem of the sheet.

Hope you like it. Comment if you have any doubt.

LIKE | SHARE | SUBSCRIBE

[deepaksarvepalli]

Today i felt that i am not waste in solving problems cause i too think same approaches before watching the vedio

[mohammedwaseem]

Bro i wrote the same code in c++ it's giving TLE or output has -1

[hariprasadcr]

Isn't the "int xx = a[i-1]" is faulty when i=0, (similarly for j and k) ?

[divyanshuchaudhari]

Surprised how is not getting index out of bound error for int xx=a[i-1] when i=0 and not incremented in the loops above it. Looks like some problem with GFG test cases.

[yuktikashyap]

For Java u can keep a chk😅
Like
while(i-1>-1 && i<n1 && A[i] == A[i-1] )
And same can be done for j and k while loops

[divyanshuchaudhari]

Java Solution:

class Solution
{
ArrayList<Integer> commonElements(int A[], int B[], int C[], int n1, int n2, int n3)
{
int x = 0;
int y = 0;
int z = 0;
ArrayList<Integer> result = new ArrayList<>();
while(x<n1 && y<n2 && z<n3){
if(A[x]==B[y] && B[y]==C[z]){
result.add(A[x]);
x++;
y++;
z++;
}
else if(A[x]<B[y]){
x++;
}
else if(B[y]<C[z]){
y++;
}
else{
z++;
}
if (x>=1 && x<n1){
int xx = A[x-1];
while(x<n1 && A[x]==xx){
x++;
}}
if (y>=1 && y<n2){
int yy = B[y-1];
while(y<n2 && B[y]==yy){
y++;
}}
if (z>=1 && z<n3){
int zz = C[z-1];
while(z<n3 && C[z]==zz){
z++;
}}
}
return result;
}
}

[ayushvats]

in the second method instead of using all those 3 loops at end we can simply add a check that if the elements once get added to our answer vector, don't add it again if(A[i] not present in vector) then only add

[rajput_warriors]

we can also store first the common elements in set and then convert in vector that reduces time complexity minutely

[sudhanshoosarage]

Update last else condition
write:
elser if( C[k] < A[i] ){
k++;
}

Above code will not work for Input:
1, 2, 3
1, 2, 3
1, 2, 3

[shreem]

Is c++ language more concise than java?? I was trying to solve this programs in java but it was taking so much of tym to understand things in java but after seeing ur vids i switch to c++.What should i do i also want to learn java

[vishalmishra]

It shows array index out of bound if run java code

[rohandevaki]

at 8:47, isnt the time complexity of this approach o(k^2), where k = n1+ n2+ n3 ? you are using two while loops, how is it O(k) ?

[roshankonj]

Simple logic to store unique elements as the given are all sorted, we can check last element present in our ans vector is already added or not.

if((a[i] == b[j]) && (a[i] == c[k]))]
{
if(ans.empty() || ans.back() != a[i])
ans.push_back(a[i]);
i++; j++; k++;
}

[dishadugad]

what if i or j or k remains 0 then we will compare with -1th element

[baigankabharta]

first approach can also be solved using a single hashmap that way space complexity will reduced to O(n1) only

[lalit-singh-bisht]

bhai ismein xx = a[i-1] yy=b[j-1] zz=c[k-1], toh isss question mein why the it's not giving segment fault, since when i=0, j=0, k=0 then it will try of access a[-1], b[-1].c[-1]....

[shellindebted]

Thank you Sir for the wonderful explanation. It helped me a lot.

[Aryansingh-fkhy]

giving index out of range at x=ar1[i-1], then the consecutive loop defined for the same.Help me with this.GFG code for python has not mentioned this condition.

[rahulscapes]

I dont know about C++ but in python, we check if the A[i] is already in Answer array, if not we append, else we leave it alone, I will attach the source code in reply

[rohandevaki]

also for the second approach we are getting index out of bounds error, you didnt handle it?