## find intersection of elements in two arrays

November 26, 2012 1 Comment

Assume two arrays, ‘A’ of size ‘m’ and ‘B’ of size ‘n’

**case 1:** Two arrays are unsorted

Here we pick one of the array and load it into hash implemented data structure, i.e, HashSet and then proceeds further to find intersection of elements.

Since hashed data structure’s complexity is O(1), the total complexity to find intersection of elements the complexity would become

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

**Algorithm Space Complexity: O(m) **

public void intersect1(int[] a, int[] b) { HashSet<Integer> hs = new HashSet<Integer>(); for (int i = 0; i < b.length; i++) { hs.add(b[i]); } for (int i = 0; i < a.length; i++) { if(hs.contains(a[i])) { System.out.println(a[i]+" is present in both arrays"); } } }

**pros:**

best algorithm when compared to all others provided one implements appropriate hashcode method

**cons:**

when the size of the data structure grows too high, it might lead to hash collisions

**Case 2:** Two arrays are sorted

For every element in array A, do a binary search in array B (instead of linear search as shown in case-1), so here for every value in ‘A’ we go through log(n) interations in ‘B’ to find out if element in ‘A’ exists in ‘B’

**Algorithm Time Complexity: O(m)*O(logn)**

public void intersect(int[] a, int[] b) { for(int i=0; i<a.length; i++) { int val = binarySearch(b, a[i], 0, a.length); if(val == b[j]) { System.out.println(a[i]+" is present in both arrays"); break; } } }

**case 3:** Two arrays are unsorted

Brute force algorithm: For every element in array A, traverse through all the elements of array B and find out if the element exists or not.

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

In Java

public void intersect(int[] a, int[] b) { for(int i=0; i<a.length; i++) { for(int j=0; j<b.length; j++) { if(a[i] == b[j]) { System.out.println(a[i]+" is present in both arrays"); break; } } } }

** pros:**

works well for smaller arrays

works for unsorted arrays

**cons:**

order/complexity is directly proportional to the product of size of arrays, this can take huge time for arrays of larger lengths

## Recent Comments