find intersection of elements in two arrays

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