Trapdoor : Nifty Algorithms

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<a.length && j<b.length) {
    if (a[i] == b[j]) {
      intersection[] = a[i]; // or b[i], obviously
      i++;
      j++;
    } else if (a[i] > b[j]) {
      j++;
    } else {
      i++;
    }
  }