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

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey