# # Single Number

Posted: Jun 29, 2021 Updated: Aug 6, 2022

Single Number

Get the code & notes on

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] Output: 1 since 1 appears once.

Ex 2) Input: nums = [4, 1, 2, 1, 2] Output: 4 since 4 appears once.

Ex 3) Input: nums = [1] Output: 1 since 1 appears once.

## # 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]:

• 1st Iteration:

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

• 2nd Iteration:

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

• 3rd 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.

## # 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));