Sorted-Union of two unsorted Arrays

algo

Using O(m+n) time and approx. O(m+n) extra space
//assume the arrays to be [a] and [b]
function UniteAndSort( a, b ){
  //initialize i and j to 0
  var i=0;
  var j=0;
  var c = [];
  var d = [];
  while ( (i+j) < (a.length + b.length) ) {
    if ( i < a.length ) {
      c[ a[i] ] = a[i];
      i++;
    }
    if ( j < b.length ) {
      c[ b[j] ] = b[j];
      j++;
    }
  }

  //We obtain a sparse array 'c'
  //Now our objective is to reduce the
  //sparsity/sparseness of it by using another array
  //Assuming that we're not altering our original arrays

  for(var i=0, j=0; i<c.length; i++){
    if(c[i]){
      d[j] = c[i];
      j++;
    }
  }

  return d;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s