Programs to Find Common Elements between Two Unsorted Arrays

Given set of two unsorted arrays as input, the goal is to find common elements between them in an efficient way. Let’s solve this problem using the following methods i.e., Method 1: Iterative approach, Method 2: Using HashSet and Method 3: Using HashSet retainAll() method.

Example:

Input: array1 = {2,3,4,5,2,5,6,7,6,8,9,1};
       array2 = {1,3,5,7,10};

Output: Common Elements between array1 and array2: [3, 5, 7, 1]

Method 1: Iterative Approach

package com.sneppets.dsalgo.examples;

import java.util.ArrayList;
import java.util.List;

/**
 * Program to find common elements between two arrays 
 * using iterative approach
 * @author sneppets.com
 */
public class CommonElementsArraysIterative {
	
	public static void main (String[] args)
	{
		int[] array1 = {2,3,4,5,2,5,6,7,6,8,9,1};
		int[] array2 = {1,3,5,7,10};
		
		findCommonElements(array1, array2);
	}

	private static void findCommonElements(int[] array1, int[] array2) {
		
		List<Integer> commonElements = new ArrayList<Integer>();
		for(int i=0; i<array1.length; i++)
		{
			for (int j=0; j<array2.length; j++)
			{				
				if(array1[i] == array2[j])
				{
					if(!commonElements.contains(array1[i]))
					{
						commonElements.add(array1[i]);
					}
				}
			}
		}
		System.out.println("Common Elements between array1 and array2: " 
							+ commonElements);
	}
}

Output:

Common Elements between array1 and array2: [3, 5, 7, 1]

Time Complexity – O(n²) – Since nested for loops. So this is not an effective solution.

Let’s try to solve the above problem in other two different ways.

Method 2: Using HashSet

package com.sneppets.dsalgo.examples;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Program to find common elements between two arrays O(n) Time (using HashSet)
 * @author sneppets.com
 */
public class CommonElementsArraysHashSet1 {

	public static void main (String[] args)
	{
		int[] array1 = {2,3,4,5,2,5,6,7,6,8,9,1};
		int[] array2 = {1,3,5,7,10};
		
		findCommonElements(array1, array2);		
	}	

	private static void findCommonElements(int[] array1, int[] array2) {
		
		List<Integer> list = new LinkedList<Integer>();
		Set<Integer> set = new HashSet<Integer>();
		
		for(int element: array1)
		{
			set.add(element);
		}
		
		for(int element: array2)
		{
			if(set.contains(element))
			{
				list.add(element);
			}
		}
		
		System.out.println("Common elements " +
				"between array 1 and array 2: " + list.toString());		
	}
}

Output:

Common elements between array 1 and array 2: [1, 3, 5, 7]

Time Complexity: O(n+n) -> O(n). This approach is better than the above approach.

You can also use HashSet’s retainAll() method. This method helps to retain only the elements that are common between two collections. Please check the below example on how to use this method to solve the above problem.

Method 3: Using HashSet retainAll() method

package com.sneppets.dsalgo.examples;

import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Program to find common elements between two arrays O(n) Time (using HashSet's retainAll() method)
 * @author sneppets.com
 */

public class CommonElementsArraysHashSet2 {

	public static void main (String[] args)
	{
		int[] array1 = {2,3,4,5,2,5,6,7,6,8,9,1};
		int[] array2 = {1,3,5,7,10};
		
		findCommonElements(array1, array2);	
	}	

	private static void findCommonElements(int[] array1, int[] array2) {
		
		Set<Integer> set1 = new HashSet<Integer>(getIntegerArrayAsList(array1));
		Set<Integer> set2 = new HashSet<Integer>(getIntegerArrayAsList(array2));
		
		set1.retainAll(set2);
		
		System.out.println("Common elements between array1 and array2 "+ set1);		
	}

	private static Collection<? extends Integer> getIntegerArrayAsList(
			int[] array) {
		List<Integer> list = new LinkedList<Integer>();
		for(int element : array)
		{
			list.add(element);
		}
		return list;
	}
}

Output:

Common elements between array1 and array2 [1, 3, 5, 7]

Programs to Find Common Elements between Two Unsorted Arrays

Method 1: Iterative Approach

Method 2: Using HashSet

Method 3: Using HashSet retainAll() method

Recommended Posts

Reference