Iterate over New Map() and return before iteration is finished

Question

I am trying to learn a few new ways to handle lists in javascript. Basicly what this function does is it takes in an array of integers, it tries to find two matches that results in TargetSum, if it does it should return an array of those two sorted.

The issue I am having is that while this returns correct, it can be optimized due to forEach always running the full iteration.

How should I change this into returning as soon as I have a match?

function twoNumberSum(array, targetSum) {
  array = array.reduce((acc, curr) => {
    acc.set(curr, curr);
    return acc;
  }, new Map());

  let res = [];

  array.forEach(item => {
    const missingInc = targetSum - item;

    if (array.has(missingInc)) {
      res = [item, array.get(missingInc)].sort((a, b) => a > b)
    }
  })

  return res;
}

console.log(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10))

Ori Drori · Accepted Answer · 2019-10-26T20:25:01.970

You can iterate the array with for...of and return as soon as you find a pair.

Note: the check missingInc !== item exists because you use a map, and it will always find the number itself if the number * 2 === targetSum, for 5 + 5 = 10 in this case. The problem wasn't apparent in your code, because you return the last pair found.

function twoNumberSum(array, targetSum) {
  const map = new Map(array.map(item => [item, item]));
  
  for(const item of map.values()) {
    const missingInc = targetSum - item;
    
    if (missingInc !== item && map.has(missingInc)) {
      return [item, missingInc].sort((a, b) => a > b)
    }
  }

  return [];
}

console.log(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10))

Nina Scholz · Answer 2 · 2019-10-26T20:50:39.963

1

You could take a Set and the Set#values as Set.prototype[@@iterator]() for iterating the items.

For sorting take the delta of the items instead of a boolean value (Sorting in JavaScript: Shouldn't returning a boolean be enough for a comparison function?).

function twoNumberSum(array, targetSum) {
    var numberSet = new Set(array),
        gen = numberSet.values(),
        item,
        missing;

    while (!gen.done) {
        item = gen.next().value;
        missing = targetSum - item;

        if (missing !== item && numberSet.has(missing)) {
            return [item, missing].sort((a, b) => a - b)
        }
    }
}

console.log(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10))

edited Oct 26 '19 at 20:50

answered Oct 26 '19 at 20:43

Nina Scholz

376,160
25
347
392

Do you know the time complexity difference between var numberSet = new Set(array) and new Map(array.map(item => [item, item]));? Is there any pro/cons? – Joelgullander Oct 26 '19 at 20:48
you still need no map. and while `Set` stores less, it should be faster. and btw, the target sum prblem works faser with a different approach, like an object. – Nina Scholz Oct 26 '19 at 20:52

score 0 · Answer 3 · answered Oct 29 '19 at 21:30

You can have a generic generator which can return any number of results like

function* twoNumberSum(array, targetSum) {
  const sorted = array.sort((a, b) => a - b);
  const diff = sorted.map(n => targetSum - n);

  let i = 0;
  let j = sorted.length - 1;

  console.log(sorted);
  console.log(diff);

  while (i <= j) {
    if (sorted[i] < diff[j])
      i++;
    else if (sorted[i] > diff[j])
      j--;
    else
      yield [sorted[i++], sorted[j--]];
  }
}

This way the caller of the function can decide how many items it wants to read out. You can use a library like https://www.npmjs.com/package/fluent-iterable to read the first, or first eight, or last or whatever you like:

import fluent from 'fluent-iterable'

console.log(fluent(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10)).first());
console.log(fluent(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10)).take(8).toArray());
console.log(fluent(twoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10)).last());

Iterate over New Map() and return before iteration is finished

3 Answers3