For the month of April, leetcode.com is having a 30 days of code challenge, where a new problem is posted every day and you come up with a solution. The first problem is a fairly well know algorithm problem, Single Number.
The challenge asks that we define a method that, given a non-empty array of integers, where every element appears twice except for one, to find that single one.
Reading that, I knew that since we were working with an array and wanted to find the number that appears only one time, I could just use the select method and then returning it using join as an integer. Which ends up looking like this:
There it is, nice and tidy with only two lines of code! Excellent. But does it work?
It does! And it only takes 48 ms to run the above test. Awesome, now time to submit…
Oh no! But in the above example, it said it work! What happened??
Well, leetcode tests you code against 16 test inputs, each getting larger and larger, against an acceptable time of completion. Our code works all the way through to test #14, when the input test is an array with over 10,000 elements. The problem with our code is that it isn’t fast enough because select is sorting through every element individually and checking to see if it has appeared before, then starts over again with the next one, and so on. It works great with only a smaller array, but it gets too slow quickly and eventually fails the time test. This falls under the Big O realm and for more on this, check out this article.
So what do we do? Well, remember how excited we were to only have two lines of code? It proved to be a detriment, so let’s break it open a bit more and be more explicit. One possible solution is we can group the elements in the array as keys in a hash, with the number of times they appear as values. And we know, because of the instructions, that the array we pass through with have all the numbers appear twice and only twice. So using that knowledge, we can get even more explicit and have the hash delete any keys that appear more than once, and then returning the key that have a value of 1. Putting it all together, it looks like this.
This works! And it’s much faster because it’s not checking each number against all the other numbers, but rather going down the array, assigning any new number to a key value of one, and then deleting any keys that already exist until we are left with only one number, the non-duplicated element. This is one way to solve this problem, feel free to poke around leetcode and see find an even faster solution.
