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<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++;
    }
  }