How to find intersection of two unsorted arrays in java

 We are given two unsorted arrays in the problem and we have to find out the intersection of these two arrays. 

Suppose,

arr1[ ] = {1,2,3,4,5}

arr2[ ] = {1,4,7}

Output : 2

Explaination : In the inputs above we can see that 1 and 4 are common hence our output will be 2.

There are various methods to solve this problem.

1. Naive Solution : Simple brute force algorithm 

This is one of the most simple brute force we are running to find out the intersection of two arrays. Here we run a for loop for the first array and create a boolean variable . Inside the loop we run another loop and check whether two values within the array are equal or not . If they are equal then we go to the next index and skip the previous one. Again we check the same condition if the condition is not fulfilled then we run another loop and check if there is a duplicate of the value in the other array. There we have a variable res which increaments by one. In this way we get our answer.

class HindiCodingCommunity{

public static int intersection(int arr1[], int arr2[])

{

int res = 0;

for(int i= 0; i< arr1.length ; i++)

{

boolean flag = false;

for(int j = 0; j< i-1 ; j++){

if(arr1[j]==arr1[i]){

flag = true;

break;

}

}

if(flag==true){

continue;

}

for(int j=0 ; j<arr2.length ; j++){

if(arr1[i]==arr2[j]){

res++;

break;

}

}

}

return res;

}

public static void main(String args[])

{

int arr1[] = {3,6,9};

int arr2[] = {4,6,10,5,8,9};

int totalIntersection = intersection(arr1,arr2);

System.out.println(totalIntersection);

}

}

Output : 2

Time Complexity : O(m*(m+n))

where m = length of first array and  n= length of second array

2. Efficient Solution : Using hashset 

We can solve this problem using the hashset which is nothing but a set in java. First of all we insert all the values of the array one into the hashset . Then we iterate over the second array and check whether the element in second array is present in the first array or not . Since here contains method takes O(1) time thats the reason we are able to find the intersection in less time.

import java.io.*;

import java.util.*;

class HindiCodingCommunity{

public static int intersection(int arr1[], int arr2[])

{

HashSet<Integer> hs = new HashSet<Integer>();

for(int i=0; i<arr1.length; i++)

hs.add(arr1[i]);

int res =0;

for( int j =0 ; j<arr2.length ; j++){

if(hs.contains(arr2[j])){

res++;

hs.remove(arr2[j]);

}

}

return res;

}

public static void main(String args[])

{

int arr1[] = {3,6,9};

int arr2[] = {3,6,10,5,8,9};

int totalIntersection = intersection(arr1,arr2);

System.out.println(totalIntersection);

}

}

Output  : 3

Time Complexity : O(m+n)

where m = length of first array and  n= length of second array