In this article, we will see Java programs to find the intersection of two unsorted arrays of elements. In other words, the resulting array should only contain elements that appear in both the arrays.
For example, if the first array is [5,4,1,6,2] and second array is [6,8,2,3,7], then intersection of these two arrays will be [6, 2].
Here are some approaches for solving this problem :
Solution 1:
The first approach uses the Collection’s retainAll() method to find the intersection of the two arrays.
This method retains only the elements in this collection that are contained in the specified collection . In other words, retainAll() removes from this collection all of its elements that are not contained in the specified collection.
package com.topjavatutorial;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ArrayIntersection {
public static void main(String[] args) {
List<Integer> listOne = new ArrayList<Integer>(Arrays.asList(5, 4, 1, 6, 2));
List<Integer> listTwo = new ArrayList<Integer>(Arrays.asList(6, 8, 2, 3, 7));
listOne.retainAll(listTwo);
System.out.println(listOne);
}
}
Output :
[6, 2]
Solution 2:
This approach has a simple algorithm that iterates through both the arrays to find the common elements. Although this is a simple approach, the complexity in O(n^2) as it has to loop through both arrays.
package com.topjavatutorial;
import java.util.ArrayList;
import java.util.List;
public class ArrayIntersection {
public static void main(String[] args) {
int[] arr1 = new int[] { 5,4,1,6,2};
int[] arr2 = new int[] { 6,8,2,3,7};
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr2.length; j++) {
if (arr1[i] == arr2[j]) {
list.add(arr1[i]);
}
}
}
System.out.println(list);
}
}
Output :
[6, 2]
Solution 3:
In this approach, we improve on the performance front by sorting one of the arrays and searching the elements of the other array in it.
package com.topjavatutorial;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ArrayIntersection {
public static void main(String[] args) {
int[] arr1 = { 5, 4, 1, 6, 2 };
int[] arr2 = { 6, 8, 2, 3, 7 };
List<Integer> list = new ArrayList<Integer>();
// sort one of the arrays
Arrays.sort(arr1);
// search for elements of other array in sorted array
for (int i : arr2) {
if (Arrays.binarySearch(arr1, i) > 0) {
list.add(i);
}
}
System.out.println(list);
}
}
Output :
[6, 2]
Please suggest other approaches and/or improvements and we will be happy to mention them here for everyone’s reference.
© 2017, https:. All rights reserved. On republishing this post, you must provide link to original post
I have a better solution in bigo n
But u have to use extra space biho n space
Just store all element of first array in hash map than traverse second array and find each element from hash map in bigo 1 time and if item found in array then print this……..
Thanks
Provided that every array do not contain duplicates, another approach is using a Set:
int[] arr1 = { 5, 4, 1, 6, 2 };
int[] arr2 = { 6, 8, 2, 3, 7 };
Set set = new HashSet();
for (int i: arr1){
set.add(i);
}
List list = new ArrayList();
for (int i: arr2) {
if (set.contains(i)) {
list.add(i);
}
}
System.out.println(list);
With the first loop you put all the elements of the first array into the Set and with the second loop you just check if each element of the second array is contained in the Set: if it’s true, it means that the number is contained in both the arrays and so it’s added to the result list.
The runtime complexity is lowered to O(max(n,m)) but the space complexity is raised to linear O(n), where n is the size of first array and m is the size of the second array.