Can I interest you in a Set? The set vs. the array in Javascript

Photo by Marcus Urbenz on Unsplash

A while back, I solved a Leetcode problem with an absolutely horrendous run time, only beating roughly 9% of Javascript submissions. It was the containsDuplicate problem and it’s a fairly simple one:

I initially solved it by creating an empty array for “storage”. For every number in the original array (nums), I checked if that number was contained in my storage array…and if it wasn’t, I would add it.

Technically, my approach was “IF this storage array does NOT include this number, then add the number to the storage array”. My else statement would return true if that condition was not met, in other words if the storage array DID contain the number…which would mean that the number was present at least twice in the original array. If after iterating over all the numbers in the original nums array we never found a number that WAS already included in the storage array, we would return false…which would mean that all numbers had been unique in the original array.

It certainly worked…but, as I mentioned above, it was a pretty terrible run time. I knew that there had to be a better way, so I set out to look for one. That’s when I came upon the Set object.

According to MDN Web Docs:

Set objects are collections of values. You can iterate through the elements of a set in insertion order. A value in the Set may only occur once; it is unique in the Set's collection.

So right off the bat we see one big difference between a Set and an Array. All values in a Set are going to be unique, whereas an Array has no such constraint…if you choose, you can repeat a value in an Array as many times as you like.

Another very important distinction between the two is that, while both Sets and Arrays are “collections”, a Set is considered a keyed collection, whereas an Array is considered an indexed collection. The former, as its name implies, is a collection that uses keys…and the elements are iterable in the order of insertion. Most people with even a little exposure to Javascript are pretty familiar with the indexed nature of an Array…data is ordered by an index value and you can reference elements via that index.

Most sources consider a Set a complement to an Array…with Sets having simpler syntax than Arrays and being useful in situations where we only need to access basic operations. That being said, though, there is one case in which Sets have a distinct advantage over Arrays and it is this scenario that was useful in improving the run time of my Leetcode solution! This is the case where we are trying to verify whether an element exists in a collection.

While I used includes() for my storage array, I can use has() for my storage set….and the has() method drastically boosts performance time!

Improved run time!

Look at that! I went from beating only 9% of Javascript submissions to beating almost 76% of submissions! This is because searching for elements in a Set tends to have an O(1) complexity, while searching operations in an array tend to have O(n) complexity. So my final solution, which incorporates Set, looks like this:

One thing to keep in mind. Memory usage definitely increased with the Set…with me beating 75% of submissions using an array vs beating only 48% of submissions using a set. That being said, the gain in performance was significantly better than what was sacrificed in memory usage; the solution that works best for you is going to be specific to your unique constraints in solving the problem.