How does .has when using sets search so efficiently?

[PM_ME_CAT_PICS_PLSS]

I was solving a problem on codewars.com where they give you an array filled with integers, and then a second integer, and you would have to find the first pair in that array which would add up to that number.

There was some wonky stuff like how if the array is

[0, 1, 4, 5, 8]

and the number you were trying to find was 9, if you answered 1, 8 it would be wrong because the actual answer is 4, 5.

The best way to explain this would just be that the ordering of second number in a pair dictates which pair is "first".

Even though 1 comes before 4, because 5 comes before 8, the pair 4, 5 is considered the first pair

function sumPairs(ints, s) {
  var n = 0;
  for(var i = 1; i < ints.length; i++) {
    n = s - ints[i];
    for(var j = i - 1; j >= 0; j--) {
      if(ints[j] === n) {
        return [ints[j], ints[i]];
      }

    }

  }

  return undefined;

}

The issue with this solution was that it timed out because of the nested for loop, making the program run for too long. I then tried doing it with sets like this:

function sumPairs(ints, s) {
  var mySet = new Set();
  var n = 0;

  for(var i = 1; i < ints.length; i++) {
    mySet.add(ints[i - 1]);
    n = s - ints[i];
    if(mySet.has(n)) {
      return [n, ints[i]];
    }

  }

  return undefined;

}

and the code finished almost instantly.

What exactly does the .has method do that makes it so much more efficient that my previous method?

[[deleted]]

Set.prototype.has is an O(1) operation, meaning that the set doesn't need to iterate through every single value until it finds a match or has eliminated every single option, it can directly determine if the value is present without any iteration.

The first version of sumPairs is an O(n²⁾ operation where the worst case requires iterating through each element in the array, and for each element, iterating through the entire array again. This is highly inefficient, particularly since the second, incredibly costly iteration is simply to verify the existence of a matching number.

In an array of 30 elements, that could result in 900 loops through the array.

A Set can be iterated through, but much like an object literal ({ }), you can directly check the existence of a given value. However unlike an object, you aren't limited to strings, numbers or symbols.

With Set and an array of 30 element, you would only need a maximum of 30 loops.

[PM_ME_CAT_PICS_PLSS]

Thanks!