This post is about writing a Java program to find common elements between two given arrays. It is a common interview question where it may be asked with a condition not to use any inbuilt method or any inbuilt data structure like List or Set or you may be asked to write using any inbuilt data structure.
Here we'll see Java program to find common elements between two arrays using both approaches.
1. Find Common Elements Between Two Arrays With Nested Loops - Java Program
If you are using nested loops approach to find common elements between two arrays then you can loop through one of the arrays in the outer loop and then traverse through the other array in an inner loop and compare the element of the outer array with all the elements of the inner array. If similar element is found print it and break from the inner loop.
Find common elements between two given arrays of integers
public class FindCommonElement {
public static void main(String[] args) {
int[] numArray1 = {1, 4, 5};
int[] numArray2 = {6, 1, 8, 34, 5};
// Outer loop
for(int i = 0; i < numArray1.length; i++){
for(int j = 0; j < numArray2.length; j++){// inner loop
if(numArray1[i] == numArray2[j]){
System.out.println(numArray1[i]);
break;
}
}
}
}
}
Output
1 5
Find common elements between two arrays of strings
Logic to find common elements between two arrays remains same in case of array of Strings. Only thing that changes is how you compare, with Strings you will have to use .equals method.
public class FindCommonElement {
public static void main(String[] args) {
String[] numArray1 = {"Java", "Scala", "Python"};
String[] numArray2 = {".Net", "Scala", "Clojure", "Java",
"Java Script", "Python"};
// Outer loop
for(int i = 0; i < numArray1.length; i++){
for(int j = 0; j < numArray2.length; j++){// inner loop
if(numArray1[i].equals(numArray2[j])){
System.out.println(numArray1[i]);
break;
}
}
}
}
}
Output
Java Scala Python
Time and Space Complexity of This Approach
If first array has n elements and second array has m elements. Then outer loop runs n times and the inner loop may run upto m times. So, the time complexity is O(n X m).
No Extra space is needed in this approach so space complexity is O(1).
2. Find Common Elements Between Two Arrays Using HashSet - Java Program
If you are asked to write Java program to find common elements between two arrays where you can use inbuilt data structures then using HashSet provides a better performing solution than solution using nested loops.
Steps for solution are as given below
- Add all the elements of the first array in the HashSet.
- For each element of the second array, check if it is already in the set. If yes, that means a common element.
- Store such common elements in a separate Set. That way you won't get duplicates.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CommonElementArray {
public static void main(String[] args) {
String[] strArray1 = {"Java", "Scala", "Clojure"};
String[] strArray2 = {".Net", "Scala", "Java", "Java Script", "Python"};
CommonElementArray obj = new CommonElementArray();
obj.findCommonElements(strArray1, strArray2);
}
public void findCommonElements(String[] strArray1, String[] strArray2) {
Set<String> set = new HashSet<>();
Set<String> commonElements = new HashSet<String>();
// Add elements of first array in HashSet
for(String s: strArray1) {
set.add(s);
}
for(String s: strArray2) {
// check element (of second array) is already in the set
// if yes that means a common element, store it in another set
if(set.contains(s))
commonElements.add(s);
}
System.out.println("Common elements are- " + commonElements);
}
}
Output
Common elements are- [Scala, Java]
Time and Space Complexity of This Approach
If first array has n elements and second array has m elements. Then adding all the elements of the first array to the Set takes O(n) time because adding element to the HashSet is O(1) thus for n elements it is O(n).
Verifying that element is already there or not using contains is O(1) operation. So, for m elements it is O(m).
So, the total time complexity is O(n + m).
Extra space requirement is there for adding n elements in the HashSet and common elements (let's say k) in another Set. So, the space complexity is O(n + k)
That's all for this topic How to Find Common Elements Between Two Arrays Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-