Find indices of two numbers such that they add up to a target

Question

The task

...is taken from leetcode

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums1 = 2 + 7 = 9, return [0, 1].

const lst = [11, 7, 15, 2]
const target = 9;

My imperative solution

function findIndexOfSumPair(lst, trgt) {
  const len = lst.length;
  for (let i = 0; i < len; i++) {
    const found = lst.findIndex(x => trgt - lst[i] === x);
    if (found !== i && found !== -1) {
      return [found, i];
    }
  }
}

console.log(findIndexOfSumPair(lst, target));

My functional solution

const findIndexOfSumPair2 = (lst, trgt) => {
  return lst.reduce((res, x, i) => {
    const j = lst.findIndex(y => target - x === y);
    return j !== -1 ? [i, j] : res;
  });
};

console.log(findIndexOfSumPair2(lst, target));

The disadvantage with my functional solution is that reduce iterates till the end of the array - even though it may have found a solution already. I tried to come up with a functional that stops iterating once it found a solution. I could come up with this. However it is too verbose and relies on side-effects (which doesn't make it functional anymore):

const findIndexOfSumPair3 = (lst, trgt) => {
  let res;

  lst.some((x, i) => -1 !== lst.findIndex((y, j) => {
    if (i !== j && trgt - y === x) {
      res = [j, i];
      return true;
    }
  }));
  return res;
};

console.log(findIndexOfSumPair3(lst, target));

Do you know an elegant and efficient functional solution?

Answer 1

Both your solutions work, however they are inefficient. A warning sign is when you need to iterate the array you are iterating. Even if the inner iteration can exit early, always consider the worst possible situation.

return lst.reduce((res, x, i) => {  // << first iteration
  const j = lst.findIndex(y => target - x === y); // << second iteration

The result is \$O(n^2)\$ time complexity

Improved search

When ever you repeat a search over the same data many times you should consider using a Map or a Set

In this case we can take advantage of the fact that the values we have already looked at provide information about the values we want.

If we have the arguments ([1,2,3,5], 7) as we step over each item we can build map of the items we want. For 1, we need a 6, 2 needs a 5, 3 needs a 4, and when you get to 5 you know you need that value and thus have a result.

Thus we get a solution that is \$O(n)\$ time, exchanging CPU cycles for memory (\$O(n)\$ storage)

Example 1

function find2SumTo(arr, k){
    const lookFor = new Map();
    var i = arr.length;
    while (i--) {
        if (lookFor.has(arr[i])) { return [i, lookFor.get(arr[i])]  }
        lookFor.set(k - arr[i], i);
    }
} // Note no final return as data is know to always have a result

The functional approach.

You don't have to use the built in array functions, you can add to the Array.prototype a more useful function.

// Finds information related to an item
Array.prototype.findInfo = function(cb) { // Must be function() to bind array to this
    var i = 0;
    while(i < this.length) {
        const result = cb(this[i], i++, this);
        if (result) { return result }
    }
}

With the new array function you can solve the problem with

const find2SumTo = (arr, k) => arr.findInfo((x, i) => 
      arr.findInfo((y, j) => {
           if (i !== j && k - y === x) { return [j, i] }
      });

However it is still an \$O(n^2)\$ time solution.

Imperative functional

The better functional approach is the first solution (Example 1). Functional does not mean you have to use lots of functions. It means that your solution must conform to the functional rules, no side effect, be pure. The function can be as complex as you need to avoid breaking the rules.