DEV Community

Alisa Bajramovic
Alisa Bajramovic

Posted on • Edited on

Finding the Only Single Number in an Array

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()
  //...
}

Enter fullscreen mode Exit fullscreen mode

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]) {
      //...
    }
  }
}

Enter fullscreen mode Exit fullscreen mode

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]
    }
  }
}

Enter fullscreen mode Exit fullscreen mode

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 = {};
  //...
}

Enter fullscreen mode Exit fullscreen mode

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

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

Enter fullscreen mode Exit fullscreen mode

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];
    }
    //...
  });
  //...
}

Enter fullscreen mode Exit fullscreen mode

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;
    }
  });
  //...
}

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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.

Top comments (4)

Collapse
 
khuongduybui profile image
Duy K. Bui

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

function xor(nums) {
  return nums.reduce((result, current) => result ^ current);
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
yogeshgalav7 profile image
Yogesh Galav

The Hash Lookup Approach Doesn't work with three duplicate values. Only work for duplicate values appearing twice.

Collapse
 
sdkdeepa profile image
Deepa Subramanian

Are we not suppose to solve this without using extra space?

Collapse
 
lunaceee profile image
Luna Yu

I like this solution a lot!