pedronauck/algorithms-with-es6

Just a bunch of algorithms using Javascript with ES6

algorithms-with-es6's Issues

Remove dist

Hey guys,

do you think there's an actual need for maintaining dist dir? I don't think the purpose of this project is to create something to be used somewhere, but more for study purposes.

cc @pedronauck

The `givenSum` implementation could be more efficient

The current givenSum implementation has two nested loops over the array, therefore it runs in O(N^2) time.

It could run in O(N) if, instead of scanning the entire array for each element, you'd keep track of all existing elements as keys in an object (which allows for a much faster lookup).

Here's the improved version:

let givenSumFast = (arr, sum) => {
  let nums = [];

  let elements = {};

  arr.forEach((x) => { elements[x] = true; });

  arr.forEach((y) => { 
    let x = sum - y;
    elements[x] && nums.push([x, y]);
  });

  return nums.sort((a, b) => a[0] - b[0]);
};

You can compare the run times of the two versions here (see the console for the results). For an array of 1000 random elements the slow version takes 2-4s, while the fast one always takes 0.004s.

OK, it is O(N logN) because of the sort at the end, but it's still a major improvement. And the sort is not apparently part of the spec, so it could be dropped.