2 Sum algorithm explantion?

I am a noobie in JavaScript algorithm and cannot understand this optimal solution of the 2-sum

function twoNumberSum(array, target) {
    const nums = {};
    for (const num of array) {
        const potentialMatch = target - num;
        console.log('potential', potentialMatch);
        if (potentialMatch in nums) {
            return [potentialMatch, num]
        } else {
            nums[num] = true;
        }
    }
}

Answer

So the 2-sum problem basically says “find two numbers in an array that sum to the given target, and return their index”. Let’s walk through this code and talk about what’s happening.

First, we start the function; I’m going to assume this makes sense (a function that’s called twoNumberSum that takes in two arguments; namely, array and target) – note that in JS, we don’t annotate types, so there is no return type

Now, first thing we do is create a new object called nums. In JS, objects are effectively hash maps (with some very important differences – see my note below); they store a key and a corresponding value. In JS, a key can be any string or number

Next, we start our iteration. If we do for (const a of b), and b is an array, this iterates over all the values of the array, with each iteration having that value stored in a.

Next, we subtract our current value from the target. Then comes the key line: if (potentialMatch in nums). The in keyword checks for the existence of a key: 'hello' in obj returns true if obj has the key 'hello'.

In this case, if we find this potential match, then that means we have found another number that is equal to target - num, which of course means we’ve found the other partner for our sum! So in this case, we simply return the two numbers. If, on the other hand, we do not find this potentialMatch, that means we need to keep looking. But we do want to remember we’ve seen this number – thus, we add it as a key by doing nums[num] = true (this creates a new key-value pair; namely the key is num and the value is true).

As one of the comments explained, this is just trying to keep track of a list of numbers; however, the author is trying to be clever by using a Hash Table instead of a normal array. This way, lookups are O(1) instead of O(n). For eyes not used to JS semantics, another way of explaining this code is that we build up a Map of the numbers, and then we check that map for our target value.

I mentioned earlier that using objects as hash tables isn’t the best idea; this is because if you aren’t careful, if you use user-provided keys, you can accidentally mess with what’s called the Prototype Chain. This is beyond this discussion, but a better way forward would be to use a Set:

function twoNumberSum(array, target) {
// Create a new Hash Set. Sets take in an iterable, so we could
// Do it this way. But to remain as close to your original solution
// as possible, we won't for now, and instead populate it as we go
// const nums = new Set(array);

const nums = new Set();
for (const num of array) {
  const potentialMatch = target - num;
  if (nums.has(potentialMatch)) {
    return [potentialMatch, num];
  } else {
    nums.add(num);
  }
}

Sometimes, the problem instead asks for you to return the indices; using a Map instead makes this relatively trivial. Just store the index as the value and you’re good to go!

function twoNumberSum(array, target) {
// Create the new map instead

const nums = new Map();
for (let n = 0; n < array.length; ++n) {
  const potentialMatch = target - array[n];
  if (nums.has(potentialMatch)) {
    return [nums.get(potentialMatch), n];
  } else {
    nums.set(array[n], n);
  }
}