Single Number LeetCode(#136)

This algorithm is a popular technical interview question interviewers give. I had it myself! Without further ado, lets get into it. I’ll solve this question via the optimized solution using a hash table data structure. If you want to see the solution to the problem, it is at the bottom of this article. Otherwise, here are the steps to solving it and why:

Question:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Understanding:

1. “Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.”

An example that follows this is:

nums = [1,2,1,2,4]

Since four is the non-repeating number, that is our output. For the sake of understanding this from my interview experience, my interviewer asked me not to sort the array, so neither will we.

Solution:

1. Create a data structure

I used a hash table: {}

let ds = {}

2. Implement a for loop to loop through the array and go through each value.

for (let ele of nums) {
...
}

I used a for loop with this structure because, well, it’s simpler and easier to write out. I don’t need to structure specific increments, starting or ending points like the traditional for loop:

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

3. Write logic to store a key in the hash and the value. We will be using the hash as a frequency counter to keep track of all the indices in the array as keys and how often they accumulate (frequency).

for (let ele of nums) {
ds[ele] = (ds[ele] || 0) + 1
}

This logic means that ds[ele] on the left side of the equal sign is assigning each iteration in the array as the key. The right side of the equal sign means, ‘either the key or 0 + 1’. Confusing? That’s okay. It will default to zero since you can’t assign key and value pairs like this: ds[ele] = ds[ele] (this results in the value being ‘Not a Number’ or NaN, so it will default to zero instead.).

The hash or data structure will look like this:

ds = { '1': 2, '2': 2, '4': 1 }

4. Iterate through the hash

Now that we set up our hash through a frequency counter made with a for loop, we can now iterate through the hash and determine which value has a frequency of ‘1’ and return the key. So let’s set up another for loop with some logic that states: ‘if the value is equal to 1, return the key’.

for (let i in ds) {
   if (ds[i] === 1) return i
}

All done! It’s that easy. Here is what the function will look like overall.

var singleNumber = function(nums) {
let ds = {}
    for (let ele of nums) {
       ds[ele] = (ds[ele] || 0) + 1
    }
    for (let i in ds) {
       if (ds[i] === 1) return i
    }
};
singleNumber([1,2,1,2,4])

The time complexity for this problem is O(N).

Thanks for reading and happy hacking!

-Crystal