loading...

Finding the Only Single Number in an Array

alisabaj profile image Alisa Bajramovic Updated on 惻3 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

One of the top interview questions, according to Leetcode, is: given a non-empty array of integers, every element appears twice except for one. Return that one element.

For example, let's say you're given the array [2, 1, 4, 4, 2]. The output of the algorithm should be 1. 2 and 4 both appear twice, and 1 appears once, so that's the only single number.

There are a number of ways to approach this problem, and in this post I'm going to talk about two main ones: sorting the array and checking the neighbors of each element, and doing a hash lookup.

Sorting and Checking Neighbors

The idea behind this approach is that, if you have a sorted array, then either the element before or the element after would be the same as the current element. If neither are the same, then that's how you know that that element is the only single number.

To do this approach, you start by creating a new variable that's equal to doing the .sort() function on the input array.

function singleNumberSortAndCheck(nums) {
  let sorted = nums.sort()
  //...
}

Then, using a for loop, walk through the sorted array and check if the element before or the element after are the same.

function singleNumberSortAndCheck(nums) {
  let sorted = nums.sort()
  for (let i = 0; i < sorted.length; i++) {
    if (sorted[i-1] !== sorted[i] && sorted[i+1] !== sorted[i]) {
      //...
    }
  }
}

If neither are equal to the current element, then that's the lone single element, and you can return it.

function singleNumberSortAndCheck(nums) {
  let sorted = nums.sort()
  for (let i = 0; i < sorted.length; i++) {
    if (sorted[i-1] !== sorted[i] && sorted[i+1] !== sorted[i]) {
      return sorted[i]
    }
  }
}

This approach uses the .sort() function, which typically has a time complexity of O(n log(n)). While this approach works, and passes tests, it has a slow runtime--slower than 70% of other JavaScript submissions.

The Hash Lookup Approach

A faster approach to this problem involves using hash tables. Hash tables are great because, on average, searching, insertion, and deletion all take O(1) time. (For a great resource on Big O, check out www.bigocheatsheet.com/.)

In this approach, I'm going to initialize a hash, then walk through the input array and check each element. If that element is already a key in the hash, then that means we've already seen it in the array, so we can delete it from the hash. If that element is not in the hash yet, we can initialize it. Finally, we can return the only key in the hash, which should correspond to the only element in the input array that is unique.

First, I'll initialize a hash.

function singleNumberWithHash(nums) {
  let hash = {};
  //...
}

Then, I'll use .forEach to walk through the input array.

function singleNumberWithHash(nums) {
  let hash = {};
  nums.forEach((num) => {
    //...
  });
  //...
}

Now, I'll check if the hash already has a key of the number that I'm on. If it does, then I will delete that key from the hash.

function singleNumberWithHash(nums) {
  let hash = {};
  nums.forEach((num) => {
    if (hash[num]) {
      delete hash[num];
    }
    //...
  });
  //...
}

If that number is not already in the hash, then we haven't yet seen it in the array, so we'll initialize it in the hash.

function singleNumberWithHash(nums) {
  let hash = {};
  nums.forEach((num) => {
    if (hash[num]) {
      delete hash[num];
    }
    else {
      hash[num] = 1;
    }
  });
  //...
}

Finally, we can return the only key in the hash, which should be the only single number in the input array. To do this, we'll use Object.keys() and pass in the hash. It's also important to remember that Object.keys returns an array of the keys. Since we only want a value, we can simple return the 0 index of the array.

function singleNumberWithHash(nums) {
  let hash = {};
  nums.forEach((num) => {
    if (hash[num]) {
      delete hash[num];
    }
    else {
      hash[num] = 1;
    }
  });
  return Object.keys(hash)[0];
}

That's it! In the comments, please let me know if you have any questions, or if you have other approaches to this algorithm that you like.

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

I will put this here and let the curious research bitwise XOR with numbers ;)

function xor(nums) {
  return nums.reduce((result, current) => result ^ current);
}