Return true if any element of array is equal to n or sum of two elements of array is equal to n - improve performance

user_13699811 0
Viewed 170

As in title I want to return true if any element of array is equal to n or sum of two elements of array is equal to n. So if array is [1,4,5] and n is 1 or 4 or 5 or 6 or 9 I want to get true. Here's my code:

function checkArray (x, array) {
  return array.includes(x) || array.some((item, i) => array.slice(i+1).includes(x-item)); 
}

It works fine but is using "some" the best way in terms of performance? How can I improve execution speed?

Edit: Negative numbers are allowed

ecmascript-6 javascript
1 Answers

There's nothing wrong with some other than the normal performance overhead of allocating/garbage collecting a function object and spinning up a function call for each and every element of the array.

It's pretty much always fastest to use a traditional for loop, but this is generally a micro-optimization that should only be used as a last resort -- refactoring from idiomatic high-level callback-driven JS code to for loop only offers a constant factor speedup.

Before resorting to that, I'd recommend lowering your time complexity: Array#includes is O(n), as is Array#slice. Doing these operations in a nested loop is O(n^2).

You can try the classic "space vs time" tradeoff and use a set to store each element you've seen so far. If n - currentElement === something in the set, you've located two numbers that sum to n.

const oneOrTwoElementsEqualN = (arr, n) => {
  const seen = new Set();
  return arr.some(e => {
    if (e === n || seen.has(n - e)) {
      return true;
    }
    
    seen.add(e);
  });
};

console.log(oneOrTwoElementsEqualN([1,2,3], 5));
console.log(oneOrTwoElementsEqualN([1,2,3], 2));
console.log(oneOrTwoElementsEqualN([1,2,3], 6));

Note that this a slight variant of the "two sum" problem.

user_62433520
Related