The Sampson Project

Picking Unique Values from a JavaScript Array

« Back to Blogs

How to keep your operation O(n)


There are many times where you might need only unique values from an array. In JavaScript there are no helpers to get that done unless you want to include a library like Underscore or Lodash. So while trying to avoid an entire library just for a single operation how do you retrieve the values you need while keeping your time and space complexities low?

Brute Force It

Let's start by looking at the brute force solution:


function getUnique(array){
  var unique = [];
  // loop through the input array
  inputLoop: for(var i = 0; i < array.length; i++){
    // check if the value at this index is already in the unique array
    for(var n = 0; n < unique.length; n++){
      // skip to next item in input if value exists in unique
      if(array[i] === unique[n]) continue inputLoop;
    }
    unique.push(array[i]);
  }
  // return the unique array;
  return unique;
}

The solution above works by checking whether each array item exists in the unique array before pushing to it. It is space effecient, only adding unique values to a single return array, but becomes more and more computationally inneficient as the unique array grows.

Let's add a hash to decrease the time complexity of checking existing values.

Efficient But Improvable


function getUnique(array){
  var unique = [], uniqueHash = {};
  // loop through the input array
  for(var i = 0; i < array.length; i++){
    // skip to next item in input if value exists in unique hash
    if(uniqueHash[array[i]]) continue;
    // set value in hash and push to unique
    uniqueHash[array[i]] = true;
    unique.push(array[i]);
  }
  // return the unique array;
  return unique;
}

This can be an excellent solution for its constant time checking of whether a value is unique. The problem is that it needs both and an array and a key value pair for every item. That makes it a bit space inneficient. With a few tweaks, it may be just what we're looking for.

Shrinking It Down


function getUnique(array){
  var unique = {};
  // loop through the input array
  for(var i = 0; i < array.length; i++){
    // set the value as a key on the hash. Duplicate values will be overwritten
    unique[array[i]] = "";
  }
  // return the unique hash keys as an array;
  return Object.keys(unique);
}

K.I.S.S. at its finest. No if statements, no extra variables, and most importantly, no nested loops.

This solution works by simply overwriting values for already existing keys. By returning just the keys from the hash, you dont even need an additional return array. This 5 line solution will keep your code small and efficient.