Given two arrays and our task is to find their common elements.
Examples:
Input: Array1 = [“Article”, “for”, “Geeks”, “for”, “Geeks”],
Array2 = [“Article”, “Geeks”, “Geeks”]
Output: [Article,Geeks]Input: Array1 = [“a”, “b”, “c”, “d”, “e”, “f”],
Array2 = [“b”, “d”, “e”, “h”, “g”, “c”]
Output: [b, c, d, e]
Using Iterative Methods
Approach:
- Get the two java Arrays.
- Iterate through each and every element of the arrays one by one and check whether they are common in both.
- Add each common element in the set for unique entries.
Java
// Java Program to find common elements// in two Arrays// Using iterative methodimport java.io.*;import java.util.*;class GFG { 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]) { // add common elements set.add(arr1[i]); break; } } } for (String i : set) { System.out.print(i + " "); } } // main method public static void main(String[] args) { // create Array 1 String[] arr1 = { "Article", "in", "Geeks", "for", "Geeks" }; // create Array 2 String[] arr2 = { "Geeks", "for", "Geeks" }; // print Array 1 System.out.println("Array 1: " + Arrays.toString(arr1)); // print Array 2 System.out.println("Array 2: " + Arrays.toString(arr2)); System.out.print("Common Elements: "); // Find the common elements FindCommonElemet(arr1, arr2); }} |
Output
Array 1: [Article, in, Geeks, for, Geeks] Array 2: [Geeks, for, Geeks] Common Elements: Geeks for
Time Complexity: O(n^2)
Auxiliary Space: O(n)
Using Hashsets:
By using the retainAll() method of the HashSet we can find the common elements between two arrays.
Syntax:
// This method keeps only the common elements // of both Collection in Collection1. Collections1.retainAll(Collections2)
Approach :
- Get the two Arrays.
- Create two hashsets and add elements from arrays tp those sets.
- Find the common elements in both the sets using Collection.retainAll() method. This method keeps only the common elements of both Collection in Collection1.
- Set 1 now contains the common elements only.
Below is the implementation of the above approach:
Java
// Java Program to find common elements// in two Arrays using hashsets// and retainAll() methodimport java.io.*;import java.util.*;class GFG { // function to create hashsets // from arrays and find // their common element public static void FindCommonElements(int[] arr1, int[] arr2) { // create hashsets Set<Integer> set1 = new HashSet<>(); Set<Integer> 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); } // use retainAll() method to // find common elements set1.retainAll(set2); System.out.println("Common elements- " + set1); } // main method public static void main(String[] args) { // create Array 1 int[] arr1 = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }; // create Array 2 int[] arr2 = { 100, 9, 64, 7, 36, 5, 16, 3, 4, 1 }; // print Array 1 System.out.println("Array 1: " + Arrays.toString(arr1)); // print Array 2 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: O(n)
Auxiliary Space: O(n)
Using HashSet:
Approach:
- Add all elements of first array into a hashset.
- Iterate the second array and check whether element present in hashset using contains method. If contains == true, add the element to result in array.
Below is the implementation of the above approach:
Java
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, 4, 5, 6, 9, 8 }; findCommonElements(arr1, arr2); /* expected output {1,3,4,5,6} coming from the above written code that is right 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.remove(arr2[i]); /* remove common elements from hashmap to avoid duplicates*/ System.out.print(arr2[i] + " "); } } }} |
Output
1 3 4 5 6
Time Complexity: O(n)
Auxiliary Space: O(n)
