Nifty Algorithms

Algorithms I find satisfying in some way

Array Intersection

O(n+m) on pre-sorted arrays

• Arrays must be sorted
• Start at the beginning of both arrays
• Compare elements
• If they are equal, add to intersection and advance both pointers
• If they are not, advance the pointer of the smaller element

var a[] = {2,4,6,8,10};
  var b[] = {1,2,8,9,11,12};

var intersection = new Array(); var i = 0; var j = 0; while(i b[j]) { j++; } else { i++; } }