Program to Find the Common Elements between two Arrays in Java
In this article, we are going to learn how to find the common elements between two arrays using Java. Here, we use different approaches in Java to find the common elements. We are also going to calculate the time complexities of every program also.
Here, we are using the following approaches to find the common elements between two arrays:
- Using Iterative method
- Using Hash sets
Iterative Method Program
In this approach, we follow the following things:
- Acquire the two Java Arrays.
- Check to see if there are any elements that are shared by both arrays by iterating through each element one by one.
- To create individual entries, add each shared element in the set.
Example 1:
import java.io.*;
import java.util.*;
class JTP {
private static void FindCommonElemet(String[] arr1,
String[] arr2)
{
Set<String> set = new HashSet<>();
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr2.length; j++) {
if (arr1[i] == arr2[j]) {
set.add(arr1[i]);
break;
}
}
}
for (String i : set) {
System.out.print(i + " ");
}
}
// main method
public static void main(String[] args)
{
// Creating Array 1
String[] arr1
= { "Hi", "I", "Am", "a", "Robot" };
// Creating Array 2
String[] arr2 = { "I", "Am", "Robot" };
// Printing Array 1
System.out.println("Array 1: "
+ Arrays.toString(arr1));
// Printing Array2
System.out.println("Array 2: "
+ Arrays.toString(arr2));
System.out.print("Common Elements: ");
FindCommonElemet(arr1, arr2);
}
}
Output:
Array 1 - { Hi, I, Am, a, Robot }
Array 2 - { I, Am, Robot}
Common elements – I Am Robot
Time Complexity of the program is: O(n^2)
Auxiliary Space: O(n)
Using Hash sets
In this approach, we follow the following things:
- Acquire the two Arrays.
- Create two hash sets then fill them with elements from arrays.
- Utilize the Collection.retainAll() method to identify the shared elements between the two sets. Only the elements that are shared by both Collections are kept in Collection1 by this method.
- Now, the common items are in Set 1.
Example 2:
import java.io.*;
import java.util.*;
class JTP {
public static void FindCommonElements(int[] arr1,
int[] arr2)
{
// create hashsets
Set set1 = new HashSet<>();
Set set2 = new HashSet<>();
// Adding elements from array1
for (int i : arr1) {
set1.add(i);
}
// Adding elements from array2
for (int i : arr2) {
set2.add(i);
}
set1.retainAll(set2);
System.out.println("Common elements- " + set1);
}
// main method
public static void main(String[] args)
{
int[] arr1
= { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 };
int[] arr2 = { 100, 9, 64, 7, 36, 5, 16, 3, 4, 1 };
System.out.println("Array 1: "
+ Arrays.toString(arr1));
System.out.println("Array 2: "
+ Arrays.toString(arr2));
FindCommonElements(arr1, arr2);
}
}
Output:
Array 1 - [1 ,4 ,9 ,16 ,25 ,36 ,49 ,64 ,81 ,100]
Array 2 – [100, 9, 64, 7, 36 ,5 ,16 ,3 ,4 , 1]
Common elements – [16 ,64 ,1 ,4 ,36 ,100 ,9]
Time complexity for the following program is: O(n)
Auxiliary space for the following program is: O(n)
Example 3:
In this approach, we follow the following things:
- Create a hashset with the first array's whole contents.
- Utilizing the includes method, iterate the second array to see if any of the elements are present in the hashset.
- Add the element to the result in the array if contains
import java.util.HashMap;
public class CommonElementsOfArrays {
public static void main(String[] args)
{
int[] arr1 = new int[] { 1, 2, 3, 4, 5, 6, 7 };
int[] arr2 = new int[] { 1, 3, 5, 6, 9, 8, 3 };
findCommonElements(arr1, arr2);
/* expected output {1,2,3,5,6}
coming from the above written code {1,2,3,5,6,3}
that is wrong if not please correct me
*/
}
public static void findCommonElements(int arr1[],
int arr2[])
{
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < arr1.length; i++) {
if (hashMap.containsKey(arr1[i])) {
hashMap.put(arr1[i],
hashMap.get(arr1[i]) + 1);
}
else {
hashMap.put(arr1[i], 1);
}
}
for (int i = 0; i < arr2.length; i++) {
if (hashMap.containsKey(arr2[i])
&& hashMap.get(arr2[i]) > 0) {
hashMap.put(arr2[i],
hashMap.get(arr2[i]) - 1);
System.out.print(arr2[i] + " ");
}
}
}
}
Output:
1
3
4
5
6
Time Complexity for the above program is: O(n)
Auxiliary Space for the above program is: O(n)