True mastery came with a continues repetition of basic.
I always ask some simple puzzles for whiteboard interview for “trivial” coding task.
Just for 1 liner just for 5 minutes. The goal is check if candidate could code.
Belive me it is a lot of cases when they couldnt (it is a topic for next time).

Challenge

Write a function that get unique values from array

One of modern solutions

1
2
3

function setToArray (arr) {
    return [...new Set(arr)];
  }

The Full Story and Real Challenge

Get unique elements of the array of simple values.
The horror part - It should run on IE 7 !!!
it should run fast as part of intensive calculations
We could use an external lib

Solutions

General notes. I have learned that all laws of computer science do not always work with JS. Any native function could be tremendously faster of any algorithms. Let’s use jsperf for test and measurements.

Test data

Data drive perf results. So we could have worts cases and so one.
Let’s generate data randomly and make sure that we have duplicated values.

1	const rnd = () => Math.floor((Math.random() * 10000000) + 1) % 200;

The size of the array could have an impact for tests. So let’s have 10, 200 and 10000 length

var a10 = [] ; a200 = [] ; a10000 = [];
var i = 0;

while (i++ < 10000 ) {
  a10000[i] = rnd();
  if (i < 200) {a200[i] =  rnd()}
  if  (i < 10) {a10[i] =  rnd()}
}

The super modern ES6 with Sets

I know that IE6 cut the crazy amount of variant but let’s try to use the most stylish way

1
2
3

function setToArray (arr) {
    return [...new Set(arr)];
  }

looks ultra short but as you can see

How it works

We tune an array to set. we do filtering there
we need to convert iterative to an array. “…” will do it.

Filter

Filter get access to an original array.

function onlyUnique(value, index, self) {
    return self.indexOf(value) === index;
}
function uSelfIndexOf(a) {
    return a.filter( onlyUnique );;
}

How it works

So we could scan an array and remove items that have the same value but different values. To get the index, we use a native indexOf. As you see all is native methods but anyway we have O(N^2) complexity.

One littel isuue filter doc IE9.

IndexOf IE7 friendly

It is first IE7 friendly but still O(N^2) solution but with native function.

function uIndexOf (arr) {
   var r = [];
   var l = arr.length; 
  for(var j = 0 ; j < l ; j++) {
    if(r.indexOf(arr[j]) === -1) {
        r.push(arr[j]);
    }
  }
  return r;
  }

Let Sort

Well O(N^2) is too much. Native sort performs as O(N * log N). We could use it

function compare(a,b) {ruturn a-b};
function sortedUnique (arr) {
      arr.sort(compare);
      var r = [];
      for (var i = 0, l = arr.length - 1 ; i < l; i++ ) {
          if(arr[i] - arr[i+1]) {
               r.push(arr[i]);
          }
      }
      return r ;
  }

How it is work

To big CAUTIONS

sort mutate an array
default sort use a lexicology sort

1	[11, 1, 111 , 12 ,2 ,7].sort() // [1, 11, 111, 12, 2, 7]

1	[11, 1, 111 , 12 ,2 ,7].sort((a, b) => a-b )// [1, 2, 7, 11, 12, 111]

So now O(2N log N ) that much better than O(N^2). Still, we have an issue with mutability.
If it is better, we could fix it with good old slice, but it will kill all performance.

function sortedUniqueNoMutate (arr) {
      var a = arr.slice(0);
      a.sort(cmp);
      var r = [];
      for (var i = 0, l = arr.length - 1 ; i < l; i++ ) {
          if(a[i] - a[i+1]) {
               r.push(a[i]);
          }
      }
      return r ;
  }

Mutable version perform even faster that Set implementation, but if we add clone operation - it makes the function a bit faster then O(N^2) implementations

The map. O(1)

Javascript object is a hashmap. As you know read access for a hashMap is an O(1).

function uExtraMap (arr) {
  var r = [];
  var m = {}
  
   var l = arr.length ; 
  for(var j = 0 ; j < l ; j++) {
  
    if(!m[arr[j]]) {
        m[arr[j]] = true;
        r.push(arr[j]);
    }
  }
  return r;
  }

How it work

We replace a check with read from map. We get O(N). But object is extra memory. Space complexity is groving.

The map without another array.

Let’s use an object key as a source of results

function uExtraMapKeys (arr) {
  var m = {}
  var l = arr.length;
  for(var j = 0 ; j < l ; j++) {
     m[arr[j]] = true;
  }
  return Object.keys(m);
  }

How it works

The idea is simple. We accumulate values in objects keys.
We win a space but lose a speed a bit.

IE 6 object keys

As we all know Object keys are available only in IE9. So IE 6 version, but still we have extra memory ((

function uMapForIn (arr) {
  var m = {}
  var l = arr.length;
  for(var j = 0 ; j < l ; j++) {
     m[arr[j]] = true;
  }
  var r = [];
  for(v in m) {
   r.push(v);
  }
  return r;
  }

Summary

All code together with results avaliable here
perf result

PS - I use lib for It

Yep read Part II