# Single Number
# Links
Get the code & notes on
# 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]:
- 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));