# Single Number

By: J the Code Monkey
Posted: Jun 29, 2021 Updated: Jul 3, 2024

Single Number

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

Made by & for Code Monkeys 🐵