Common ELements Geeks For Geeks
class Solution
{
ArrayList<Integer> commonElements(int arr1[], int arr2[], int arr3[], int n1, int n2, int n3)
{
HashSet<Integer> set1=new HashSet<Integer>();
HashSet<Integer> set2=new HashSet<Integer>();
HashSet<Integer> set3=new HashSet<Integer>();
for(int i=0;i<n1;i++){
set1.add(arr1[i]);
}
for(int i=0;i<n2;i++){
if(set1.contains(arr2[i])){
set2.add(arr2[i]);
}
}
for(int i=0;i<n3;i++){
if(set2.contains(arr3[i])){
set3.add(arr3[i]);
}
}
/*System.out.println("set1: ");
for (Integer i : set1){
System.out.println(i);
}
System.out.println("set2: ");
for (Integer i : set2){
System.out.println(i);
}*/
Set<Integer> set4 = new TreeSet<Integer>(set3);
/*System.out.println("set3: ");
for (Integer i : set3){
System.out.println(i);
}*/
ArrayList<Integer> lList = new ArrayList<Integer>();
lList.addAll(set4);
return lList;
}
}
TIME: O(N1+N2+N3) [In GFG 2.1/3.6]
SPACE: O(N1+N2+N3)
Approach 1 :
Here we will add all the elements of array 1 in HashSet 1 so as to get only the unique elements(if there are any duplicates in array 1 also then they will be removed). After that we will traverse the second list and compare it will the HashSet 1 . if we found some common elements then they will be added into hashset2 and similarly for the third list also.
Finally, we will get HashSet 3 with common elements among three lists but it may not be sorted as HashSet is an unsorted set and for that, we will convert it into Tresset which is sorted.
In question, demand is to return the ArrayList so we will convert the tree set to ArrayList.
========================================================================
Approach 2 :
TIME: Somewhat less than O(N1+N2+N3) [In GFG 1.9/3.6]
SPACE: Somewhat less than O(N1+N2+N3)
Using One HashSet and One TreeSet only
HashSet<Integer> set1=new HashSet<Integer>();
TreeSet<Integer>q=new TreeSet<Integer>();
//Queue<Integer> q=new PriorityQueue<Integer>();
int x=0;
int y=0;
int z=0;
while(x<n1 && y<n2){
if(arr1[x]>arr2[y]){
y++;
}
else if(arr1[x]==arr2[y]){
set1.add(arr1[x]);
x++;
y++;
}
else
{
x++;
}
}
while(z<n3){
if(set1.contains(arr3[z])){
q.add(arr3[z]);
}
z++;
}
//System.out.println(q);
ArrayList<Integer> aa=new ArrayList<Integer>();
aa.addAll(q);
return aa;
If we try to use queue over here then it will work fine. But the condition is it will fail for one test case in which all elements will be equal in all three lists.
ex n1=3 arr1= 3 3 3
n2=3 arr2=3 3 3
n3=3 arr3= 3 3 3
the output we will get 3 3 3
instead, we should get only one 3
and for that only we have used TreeSet so it will accept only unique entries and in a sorted fashion.
Thanks for reading.
Hope it helped you.😇
Comments
Post a Comment