# # Single Number

## # Links

Ask Questions & Share Solutions in

## # Problem Description

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

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

## # Examples

Ex 1) Input: nums = [2, 2, 1]

Ex 2) Input: nums = [4, 1, 2, 1, 2]

Ex 3) Input: nums = [1]

## # Constraints

Each element in the array appears twice except for one element which appears only once.

## # What does Linear Runtime Mean?

A linear runtime means our solution must have a time complexity of O(n).

So, it's ok to use a loop in our solution but not a nested loop.

## # What does Using Constant Extra Space Mean?

Our given space complexity is O(n) since we're given nums which is an array of length n.

Since we want to use constant extra space, our solution must have at most O(n) space complexity.

## # Thought Process

We need to iterate over nums since we need to find out which element appears only once.

The iteration can be done using a for loop.

Now, to keep track of how many times an element has appeared in nums we can use a hash table.

A hash table is an object that maps keys to values.

Here, the key will represent the element in nums, and the value can be set to true if it has appeared once.

If the key appears again we can remove it since we know every element other than the unique element appears twice.

After removing the keys that appear twice, we just need to return the key of our hash table that appeared once.

Here's a visualization of creating our hash table which we'll denote as myObj for nums = [2, 2, 1]:

- 1
^{st}Iteration:

So, we'll store the value of nums[0] as a key in our hash table with a value of true.

2

^{nd}Iteration:

So, we'll remove the 2 key from our hash table since it has now appeared twice.

3

^{rd}Iteration:

So, we'll store the value of nums[2] as a key in our hash table with a value of true.

Now, we have reached the end of the loop, so we'll return the value of the only key left in our hash table which in this case is 1.

- 1

## # Implementation

var singleNumber = function(nums) { const myObj = {}; for (let i = 0; i < nums.length; i++) { if (myObj[nums[i]]) { delete myObj[nums[i]]; } else { myObj[nums[i]] = true; } } return Object.keys(myObj)[0]; }; nums = [2, 2, 1]; console.log(singleNumber(nums));