getDisjointList

by evgkch

JavaScript

/**
* Write a function that takes two non-decreasing sorted numeric ranges a1 and a2
* and returns a single range consisting of all a2(i) not in a1(j)
**/

// O(n + m) + memory
/* function getDisjointList(a1, a2) {
    const buffer = new Set(a1);
    return a2.filter(v => !buffer.has(v));
} */

// O(n)
function getDisjointList(a1, a2) {
  const sumLength = a1.length + a2.length;
  const result = [];
  let i = 0,
      j = 0,
      k = 0;
  for (k; k < sumLength - 1; k++)
  {
    if (a2[i] < a1[j] || a1[j] === undefined)
    {
      result.push(a2[i]);
      i++;
    }
    else if (a2[i] > a1[j])
      j++;
    else if (a2[i] === a1[j])
      i++;
  }
  return result;
}

test(getDisjointList, [0, 2, 4, 6, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
	.equals([1, 3, 5, 7, 9]);
  
test(getDisjointList, [0, 2, 4, 6, 8], [0, 1, 2, 2, 2, 2, 2, 2, 2, 9])
	.equals([1, 9]);
  
test(getDisjointList, [0, 2, 4, 4, 4, 8, 8, 10], [0, 1, 2, 2, 3, 3, 3, 9])
	.equals([1, 3, 3, 3, 9]);
  
test(getDisjointList, [4, 4, 8, 8, 10], [0, 1, 2, 2, 3, 3, 3, 9])
  .equals([0, 1, 2, 2, 3, 3, 3, 9]);

function test(fn, ...args) {
	const v = fn.call(fn, ...args);
  const vLength = v.length;
  return {
  	equals: (result) => {
    	let passed = true;
    	for (let i = 0; i < vLength; i++)
        passed = passed && (v[i] == result[i]);
      console.log('******************************************************');
      console.log('inputs:')
      console.log(...args)
      console.log('result:')
      console.log(v);
      console.log(passed ? 'Test passed! Congrats!' : 'Oh... Test failed!');
    }
  };
}