Given two sorted arrays, Write a java code to find intersection of two arrays.
For example, if the input arrays are:
arr1[] = {2, 3, 6, 7, 9, 11}
arr2[] = {4, 6, 8, 9, 12}
The common elements between these two arrays are {6, 9}.
We have discussed the problem statement. In this tutorial, I am going to discuss multiple approaches to solve the problem.
How to Find Array Intersection
Method 1 : Brute Force Approach
To find array intersection, the simplest approach is to use two loops. In this approach, we take each element of a first array and compare with each element of a second array.
The time complexity of this approach is O(mn), where m and n are the number of elements in arr1[] and arr2[].
|
1 2 3 4 5 6 7 8 9 |
//Using two for loops for(int i=0; i<arr1.length; i++ ) { for(int j=0; j<arr2.length; j++) { //If element is matched then print it if(arr1[i]==arr2[j]) { System.out.println(arr[j]); } } } |
Find first non-repeated character in a string – Java Code
Find Intersection of Two Arrays – Java Code
In our previous approach, we have used two for loops to solve this problem. Let’s improve our solution to solve this problem in single loop.
To solve this problem in single iteration, here are the steps –
i) Use two index variables i and j, initialize them with 0.
ii) If element present at arr1[i] is smaller than arr2[j] then increment i.
iii) If arr1[i] is greater than arr2[j] then increment j.
iv) If both are same then print any of the array value and increment both i and j.
The time complexity of this approach is O(m+n).
Find intersection of two arrays video tutorial
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
//Single iteration code public class Intersection { public static void main(String[] args) { int arr1[] = {2, 6, 7, 8, 9}; int arr2[] = {6, 9, 10}; /** Take two indexes, and initialize with zero. */ int i = 0; int j = 0; while(i < arr1.length && j < arr2.length) { if(arr1[i] == arr2[j]) { System.out.println(arr1[i]); i++; j++; } else if(arr1[i] > arr2[j]) { j++; } else { i++; } } } } |
Method 3: Using HashSet
We can also solve this problem using set data structure.
In this approach, we first initialize an empty set.Then, we traverse the first array and put each element of the first array in a set. Now, For every element x of the second array, we search x in the set. If x is present, then we print it.
Here, we are using additional space for this problem.
Why we are using HashSet?
Hashset does not allow duplicate elements and also the lookup time is O(1).
The time complexity of this approach is O(m+n) and it’s space complexity is O(m).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
/** Using hashset to find intersection of two arrays */ public class Intersection { public static void main(String[] args) { int arr1[] = {2, 3, 4, 5, 6}; int arr2[] = {4, 6, 7, 8, 9}; //Declare hashset HashSet<Integer> set1 = new HashSet(); //Traverse an array, put each element in a set for(int val: arr1){ set1.add(val); } /** Traverse second array values, Search the value in a set (set1), If element is found then print it. */ for(int val: arr2){ if(set1.contains(val)){ System.out.println(val); } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class Intersection { public static void main(String[] args) { Integer arr1[] = {2, 3, 4, 5, 6}; Integer arr2[] = {4, 6, 7, 8, 9}; HashSet set1 = new HashSet<>(Arrays.asList(arr1)); HashSet set2 = new HashSet<>(Arrays.asList(arr2)); set1.retainAll(set2); System.out.println(set1); } } |
Programming questions on arrays
Conclusion
I have explained multiple approaches to find intersection of two arrays in Java and discussed their time complexity. If you want to discuss any other approach then let us know through your comments.
