CODEWITHSUNDEEP
javascriptalgorithm
me-me
me-me

Reputation: 5809

Find all pairs that sum to a target value

I've been looking through this example which is a supposedly faster way of matching than using multiple loops. I've seen an explanation here but it makes absolutely no sense to me.

Can someone please break this down for me and what target - arr[i] is been used for? 

const arr = [7, 0, -4, 5, 2, 3];

const twoSum = (arr, target) => {
  let map = {}
  let results = [];
  for (let i=0; i<arr.length; i++) {
    if (map[arr[i]] !== undefined) {
      results.push([map[arr[i]], arr[i]])
    } else {
      map[target - arr[i]] = arr[i];
    }
  }
  return results;
}
console.log('twoSum = ', twoSum(arr, 5));

Upvotes: 1

Views: 1014

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23955

There seems to be a mistake in the explanation you linked to: where it says, "Our new key/value pair is 5: 5. Our hash map now contains two entries: {7: -2, 5: 5}." The new key/value (and this is achieved correctly in the code) is 5: 0.

To understand how it works suppose our array is [2, 6, 3] and the target is 5. Once we see 2, we'd like to know if the array has its partner that together sums to 5.

x + 2 = 5
x = 5 - 2
x = 3

So we're looking for 3. Now, the JavaScript map object allows us to efficiently retrieve a value if we know its key. So we set our key to 3 - this way if we see a 3 later, we can quickly respond. Remember that we haven't seen 3 yet. We're just setting the key to quickly alert us if we see it that we've seen its partner, 2, already.

Now we continue along the array. We pass by 6 but there's no key 6 in the map so we add it to the map and continue. When we get to 3, we say, "Aha!", the map having 3 is alerting us that we've seen its partner that together sums to 5. We push the result, 3 (the current arr[i]) and the value stored in the map under the 3 key (map[arr[i]]), which was the 2 we saw earlier.

Upvotes: 0

Igwe Kalu
Igwe Kalu

Reputation: 14868

The algorithm is creating pairs by examining the currently processed item with previously seen items.

So, it requires a memory for the previously seen items, and that's why map factors into the solution.

Let's analyse the loop in the solution:

  for (let i=0; i<arr.length; i++) {
    if (map[arr[i]] !== undefined) {
      results.push([map[arr[i]], arr[i]])
    } else {
      map[target - arr[i]] = arr[i];
    }
  }

It's equivalent to the following:

  for ( let i = 0; i < arr.length; i++ ) {

    // Any item in the array that's not in the memory
    // 1. should primarily be stored
    // 2. such that it's potential pair is stored as a key that's mapped to a value which is the item
    if ( map[ arr[ i ] ] === undefined ) {
      map[ target - arr[ i ] ] = arr[ i ];

      // Examine pairs only in iterations with odd numbered indices.
      // Why? - For the first iteration, the memory is empty...
      continue;
    }

    // this item’s pair is known, so store the pair in the result list
    results.push( [ map[ arr[ i ] ], arr[ i ] ] );
}

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386540

You could even make it more faster, without storing of the actual value, because you are looking for a two values and one is known, you know the other as well.

const
    arr = [7, 0, -4, 5, 2, 3],
    twoSum = (arr, target) => {
        let map = {},
            results = [];

        for (let i = 0; i < arr.length; i++) {
            if (map[arr[i]]) {                           // straight check
                results.push([target - arr[i], arr[i]]); // take delta
                continue;
            }
            map[target - arr[i]] = true;
        }
        return results;
    };

console.log('twoSum = ', twoSum(arr, 5));

Upvotes: 1

Sean F
Sean F

Reputation: 4605

Suppose target is t. Given a value x in the array, you want to know if there exists a value t - x in the array, in which case the sum is t - x + x = t.

So you go through the array, to mark the fact you see x in the array you mark the entry t - x in a map. Later when you encounter t - x in the array you check entry t - x in the map, and if it is populated then you know you previously saw x, which means you have the pair x and t - x. The way I just described it sounds like two loops through the array, but you can do these two things in just one loop and it works the same.

If a map entry is populated then you previously saw its pair value, if not populated you mark the map to see if you encounter that pair value later.

Upvotes: 1

Related Questions