Reputation: 25339

Remove duplicate values from JS array

I have a very simple JavaScript array that may or may not contain duplicates.

var names = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];

I need to remove the duplicates and put the unique values in a new array.

I could point to all the code that I've tried but I think it's useless because they don't work. I accept jQuery solutions too.

Answers (30)

passionFinder

Reputation: 129

this also helps in identifying duplicates from an array.

// Remove duplicates from the array
arr = [4,6,2,3,1,1,3,5,7,8,4,3];

arr1 = arr.reduce((acc,val,index) =>{
    if(!(acc.includes(val))){
        acc.push(val);
    }
    return acc;
},[]);
console.log(arr1);

Upvotes: -1

Vishnu

Reputation: 21

var lines = ["Mike", "Matt", "Nancy", "Adam", "Jenny", "Nancy", "Carl"];
var uniqueNames = [];

for(var i = 0; i < lines.length; i++)
{
    if(uniqueNames.indexOf(lines[i]) == -1)
        uniqueNames.push(lines[i]);
}
if(uniqueNames.indexOf(uniqueNames[uniqueNames.length-1])!= -1)

for(var i = 0; i < uniqueNames.length; i++)
{
    document.write(uniqueNames[i]);
      document.write("<br/>");
}

Upvotes: 1

HBP

Reputation: 16033

A single line version using array .filter and .indexOf function:

arr = arr.filter(function (value, index, array) { 
  return array.indexOf(value) === index;
});

ES6 approach

arr = arr.filter((value, index, array) => 
  array.indexOf(value) === index
)

Upvotes: 174

georg

Reputation: 214939

TL;DR

Using the Set constructor and the spread syntax:

uniq = [...new Set(array)];

( Note that var uniq will be an array... new Set() turns it into a set, but [... ] turns it back into an array again )

"Smart" but naïve way

uniqueArray = a.filter(function(item, pos) {
    return a.indexOf(item) == pos;
})

Basically, we iterate over the array and, for each element, check if the first position of this element in the array is equal to the current position. Obviously, these two positions are different for duplicate elements.

Using the 3rd ("this array") parameter of the filter callback we can avoid a closure of the array variable:

uniqueArray = a.filter(function(item, pos, self) {
    return self.indexOf(item) == pos;
})

Although concise, this algorithm is not particularly efficient for large arrays (quadratic time).

Hashtables to the rescue

function uniq(a) {
    var seen = {};
    return a.filter(function(item) {
        return seen.hasOwnProperty(item) ? false : (seen[item] = true);
    });
}

This is how it's usually done. The idea is to place each element in a hashtable and then check for its presence instantly. This gives us linear time, but has at least two drawbacks:

since hash keys can only be strings or symbols in JavaScript, this code doesn't distinguish numbers and "numeric strings". That is, uniq([1,"1"]) will return just [1]
for the same reason, all objects will be considered equal: uniq([{foo:1},{foo:2}]) will return just [{foo:1}].

That said, if your arrays contain only primitives and you don't care about types (e.g. it's always numbers), this solution is optimal.

The best from two worlds

A universal solution combines both approaches: it uses hash lookups for primitives and linear search for objects.

function uniq(a) {
    var prims = {"boolean":{}, "number":{}, "string":{}}, objs = [];

    return a.filter(function(item) {
        var type = typeof item;
        if(type in prims)
            return prims[type].hasOwnProperty(item) ? false : (prims[type][item] = true);
        else
            return objs.indexOf(item) >= 0 ? false : objs.push(item);
    });
}

sort | uniq

Another option is to sort the array first, and then remove each element equal to the preceding one:

function uniq(a) {
    return a.sort().filter(function(item, pos, ary) {
        return !pos || item != ary[pos - 1];
    });
}

Again, this doesn't work with objects (because all objects are equal for sort). Additionally, we silently change the original array as a side effect - not good! However, if your input is already sorted, this is the way to go (just remove sort from the above).

Unique by...

Sometimes it's desired to uniquify a list based on some criteria other than just equality, for example, to filter out objects that are different, but share some property. This can be done elegantly by passing a callback. This "key" callback is applied to each element, and elements with equal "keys" are removed. Since key is expected to return a primitive, hash table will work fine here:

function uniqBy(a, key) {
    var seen = {};
    return a.filter(function(item) {
        var k = key(item);
        return seen.hasOwnProperty(k) ? false : (seen[k] = true);
    })
}

A particularly useful key() is JSON.stringify which will remove objects that are physically different, but "look" the same:

a = [[1,2,3], [4,5,6], [1,2,3]]
b = uniqBy(a, JSON.stringify)
console.log(b) // [[1,2,3], [4,5,6]]

If the key is not primitive, you have to resort to the linear search:

function uniqBy(a, key) {
    var index = [];
    return a.filter(function (item) {
        var k = key(item);
        return index.indexOf(k) >= 0 ? false : index.push(k);
    });
}

In ES6 you can use a Set:

function uniqBy(a, key) {
    let seen = new Set();
    return a.filter(item => {
        let k = key(item);
        return seen.has(k) ? false : seen.add(k);
    });
}

or a Map:

function uniqBy(a, key) {
    return [
        ...new Map(
            a.map(x => [key(x), x])
        ).values()
    ]
}

which both also work with non-primitive keys.

First or last?

When removing objects by a key, you might to want to keep the first of "equal" objects or the last one.

Use the Set variant above to keep the first, and the Map to keep the last:

function uniqByKeepFirst(a, key) {
    let seen = new Set();
    return a.filter(item => {
        let k = key(item);
        return seen.has(k) ? false : seen.add(k);
    });
}


function uniqByKeepLast(a, key) {
    return [
        ...new Map(
            a.map(x => [key(x), x])
        ).values()
    ]
}

//

data = [
    {a:1, u:1},
    {a:2, u:2},
    {a:3, u:3},
    {a:4, u:1},
    {a:5, u:2},
    {a:6, u:3},
];

console.log(uniqByKeepFirst(data, it => it.u))
console.log(uniqByKeepLast(data, it => it.u))

Libraries

Both underscore and Lo-Dash provide uniq methods. Their algorithms are basically similar to the first snippet above and boil down to this:

var result = [];
a.forEach(function(item) {
     if(result.indexOf(item) < 0) {
         result.push(item);
     }
});

This is quadratic, but there are nice additional goodies, like wrapping native indexOf, ability to uniqify by a key (iteratee in their parlance), and optimizations for already sorted arrays.

If you're using jQuery and can't stand anything without a dollar before it, it goes like this:

  $.uniqArray = function(a) {
        return $.grep(a, function(item, pos) {
            return $.inArray(item, a) === pos;
        });
  }

which is, again, a variation of the first snippet.

Performance

Function calls are expensive in JavaScript, therefore the above solutions, as concise as they are, are not particularly efficient. For maximal performance, replace filter with a loop and get rid of other function calls:

function uniq_fast(a) {
    var seen = {};
    var out = [];
    var len = a.length;
    var j = 0;
    for(var i = 0; i < len; i++) {
         var item = a[i];
         if(seen[item] !== 1) {
               seen[item] = 1;
               out[j++] = item;
         }
    }
    return out;
}

This chunk of ugly code does the same as the snippet #3 above, ~~but an order of magnitude faster~~ (as of 2017 it's only twice as fast - JS core folks are doing a great job!)

function uniq(a) {
    var seen = {};
    return a.filter(function(item) {
        return seen.hasOwnProperty(item) ? false : (seen[item] = true);
    });
}

function uniq_fast(a) {
    var seen = {};
    var out = [];
    var len = a.length;
    var j = 0;
    for(var i = 0; i < len; i++) {
         var item = a[i];
         if(seen[item] !== 1) {
               seen[item] = 1;
               out[j++] = item;
         }
    }
    return out;
}

/////

var r = [0,1,2,3,4,5,6,7,8,9],
    a = [],
    LEN = 1000,
    LOOPS = 1000;

while(LEN--)
    a = a.concat(r);

var d = new Date();
for(var i = 0; i < LOOPS; i++)
    uniq(a);
document.write('<br>uniq, ms/loop: ' + (new Date() - d)/LOOPS)

var d = new Date();
for(var i = 0; i < LOOPS; i++)
    uniq_fast(a);
document.write('<br>uniq_fast, ms/loop: ' + (new Date() - d)/LOOPS)

ES6

ES6 provides the Set object, which makes things a whole lot easier:

function uniq(a) {
   return Array.from(new Set(a));
}

let uniq = a => [...new Set(a)];

Note that, unlike in python, ES6 sets are iterated in insertion order, so this code preserves the order of the original array.

However, if you need an array with unique elements, why not use sets right from the beginning?

Generators

A "lazy", generator-based version of uniq can be built on the same basis:

take the next value from the argument
if it's been seen already, skip it
otherwise, yield it and add it to the set of already seen values

function* uniqIter(a) {
    let seen = new Set();

    for (let x of a) {
        if (!seen.has(x)) {
            seen.add(x);
            yield x;
        }
    }
}

// example:

function* randomsBelow(limit) {
    while (1)
        yield Math.floor(Math.random() * limit);
}

// note that randomsBelow is endless

count = 20;
limit = 30;

for (let r of uniqIter(randomsBelow(limit))) {
    console.log(r);
    if (--count === 0)
        break
}

// exercise for the reader: what happens if we set `limit` less than `count` and why

Upvotes: 6214

gnujoow

Reputation: 374

The way using reduce and find.

const numbers = [1, 1, 2, 3, 4, 4];

function unique(array) {
  return array.reduce((a, b) => {
    let isIn = a.find(element => {
      return element === b;
    });
    if (!isIn) {
      a.push(b);
    }
    return a;
  }, []);
}

let ret = unique(numbers); // [1, 2, 3, 4]
console.log(ret);

Upvotes: 1

gilly3

Reputation: 91467

The top answers have complexity of O(n²), but this can be done with just O(n) by using an object as a hash:

function getDistinctArray(arr) {
    var dups = {};
    return arr.filter(function(el) {
        var hash = el.valueOf();
        var isDup = dups[hash];
        dups[hash] = true;
        return !isDup;
    });
}

This will work for strings, numbers, and dates. If your array contains objects, the above solution won't work because when coerced to a string, they will all have a value of "[object Object]" (or something similar) and that isn't suitable as a lookup value. You can get an O(n) implementation for objects by setting a flag on the object itself:

function getDistinctObjArray(arr) {
    var distinctArr = arr.filter(function(el) {
        var isDup = el.inArray;
        el.inArray = true;
        return !isDup;
    });
    distinctArr.forEach(function(el) {
        delete el.inArray;
    });
    return distinctArr;
}

2019 edit: Modern versions of JavaScript make this a much easier problem to solve. Using Set will work, regardless of whether your array contains objects, strings, numbers, or any other type.

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

The implementation is so simple, defining a function is no longer warranted.

Upvotes: 40

bodich

Reputation: 2205

Here is very simple for understanding and working anywhere (even in PhotoshopScript) code. Check it!

var peoplenames = new Array("Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl");

peoplenames = unique(peoplenames);
alert(peoplenames);

function unique(array){
    var len = array.length;
    for(var i = 0; i < len; i++) for(var j = i + 1; j < len; j++) 
        if(array[j] == array[i]){
            array.splice(j,1);
            j--;
            len--;
        }
    return array;
}

//*result* peoplenames == ["Mike","Matt","Nancy","Adam","Jenny","Carl"]

Upvotes: 10

ShAkKiR

Reputation: 929

Solution 1

Array.prototype.unique = function() {
    var a = [];
    for (i = 0; i < this.length; i++) {
        var current = this[i];
        if (a.indexOf(current) < 0) a.push(current);
    }
    return a;
}

Solution 2 (using Set)

Array.prototype.unique = function() {
    return Array.from(new Set(this));
}

Test

var x=[1,2,3,3,2,1];
x.unique() //[1,2,3]

Performance

When I tested both implementation (with and without Set) for performance in chrome, I found that the one with Set is much much faster!

Array.prototype.unique1 = function() {
    var a = [];
    for (i = 0; i < this.length; i++) {
        var current = this[i];
        if (a.indexOf(current) < 0) a.push(current);
    }
    return a;
}


Array.prototype.unique2 = function() {
    return Array.from(new Set(this));
}

var x=[];
for(var i=0;i<10000;i++){
	x.push("x"+i);x.push("x"+(i+1));
}

console.time("unique1");
console.log(x.unique1());
console.timeEnd("unique1");



console.time("unique2");
console.log(x.unique2());
console.timeEnd("unique2");

Upvotes: 26

Levi

Reputation: 1732

The following is more than 80% faster than the jQuery method listed (see tests below). It is an answer from a similar question a few years ago. If I come across the person who originally proposed it I will post credit. Pure JS.

var temp = {};
for (var i = 0; i < array.length; i++)
  temp[array[i]] = true;
var r = [];
for (var k in temp)
  r.push(k);
return r;

My test case comparison: http://jsperf.com/remove-duplicate-array-tests

Upvotes: 21

Sumit Joshi

Reputation: 1115

use Array.filter() like this

var actualArr = ['Apple', 'Apple', 'Banana', 'Mango', 'Strawberry', 'Banana'];

console.log('Actual Array: ' + actualArr);

var filteredArr = actualArr.filter(function(item, index) {
  if (actualArr.indexOf(item) == index)
    return item;
});

console.log('Filtered Array: ' + filteredArr);

this can be made shorter in ES6 to

actualArr.filter((item,index,self) => self.indexOf(item)==index);

Here is nice explanation of Array.filter()

Upvotes: 43

MBJH

Reputation: 1639

for (i=0; i<originalArray.length; i++) {  
    if (!newArray.includes(originalArray[i])) {
        newArray.push(originalArray[i]); 
    }
}

Upvotes: 6

Ashutosh Jha

Reputation: 16337

You can simply do it in JavaScript, with the help of the second - index - parameter of the filter method:

var a = [2,3,4,5,5,4];
a.filter(function(value, index){ return a.indexOf(value) == index });

or in short hand

a.filter((v,i) => a.indexOf(v) == i)

Upvotes: 67

cjjenkinson

Reputation: 367

For anyone looking to flatten arrays with duplicate elements into one unique array:

function flattenUniq(arrays) {
  var args = Array.prototype.slice.call(arguments);

  var array = [].concat.apply([], args)

  var result = array.reduce(function(prev, curr){
    if (prev.indexOf(curr) < 0) prev.push(curr);
    return prev;
  },[]);

  return result;
}

Upvotes: 3

user1429980

Reputation: 7128

ES2015, 1-liner, which chains well with map, but only works for integers:

[1, 4, 1].sort().filter((current, next) => current !== next)

[1, 4]

Upvotes: -8

shubham kucheria

Reputation: 15

var uniqueCompnies = function(companyArray) {
    var arrayUniqueCompnies = [],
        found, x, y;

    for (x = 0; x < companyArray.length; x++) {
        found = undefined;
        for (y = 0; y < arrayUniqueCompnies.length; y++) {
            if (companyArray[x] === arrayUniqueCompnies[y]) {
                found = true;
                break;
            }
        }

        if ( ! found) {
            arrayUniqueCompnies.push(companyArray[x]);
        }
    }

    return arrayUniqueCompnies;
}

var arr = [
    "Adobe Systems Incorporated",
    "IBX",
    "IBX",
    "BlackRock, Inc.",
    "BlackRock, Inc.",
];

Upvotes: -1

Mohideen bin Mohammed

Reputation: 20137

here is the simple method without any special libraries are special function,

name_list = ["Mike","Matt","Nancy","Adam","Jenny","Nancy","Carl"];
get_uniq = name_list.filter(function(val,ind) { return name_list.indexOf(val) == ind; })

console.log("Original name list:"+name_list.length, name_list)
console.log("\n Unique name list:"+get_uniq.length, get_uniq)

Upvotes: 9

Jonca33

Reputation: 3493

One line:

let names = ['Mike','Matt','Nancy','Adam','Jenny','Nancy','Carl', 'Nancy'];
let dup = [...new Set(names)];
console.log(dup);

Upvotes: 75

Sancarn

Reputation: 2824

Although ES6 Solution is the best, I'm baffled as to how nobody has shown the following solution:

function removeDuplicates(arr){
    o={}
    arr.forEach(function(e){
        o[e]=true
    })
    return Object.keys(o)
}

The thing to remember here is that objects MUST have unique keys. We are exploiting this to remove all the duplicates. I would have thought this would be the fastest solution (before ES6).

Bear in mind though that this also sorts the array.

Upvotes: 4

Dan Zuzevich

Reputation: 3831

This solution uses a new array, and an object map inside the function. All it does is loop through the original array, and adds each integer into the object map.If while looping through the original array it comes across a repeat, the

`if (!unique[int])`

catches this because there is already a key property on the object with the same number. Thus, skipping over that number and not allowing it to be pushed into the new array.

    function removeRepeats(ints) {
      var unique = {}
      var newInts = []

      for (var i = 0; i < ints.length; i++) {
        var int = ints[i]

        if (!unique[int]) {
          unique[int] = 1
          newInts.push(int)
        }
      }
      return newInts
    }

    var example = [100, 100, 100, 100, 500]
    console.log(removeRepeats(example)) // prints [100, 500]

Upvotes: 0

John Slegers

Reputation: 47061

A simple but effective technique, is to use the filter method in combination with the filter function(value, index){ return this.indexOf(value) == index }.

Code example :

var data = [2,3,4,5,5,4];
var filter = function(value, index){ return this.indexOf(value) == index };
var filteredData = data.filter(filter, data );

document.body.innerHTML = '<pre>' + JSON.stringify(filteredData, null, '\t') +  '</pre>';

Generic Functional Approach

Here is a generic and strictly functional approach with ES2015:

// small, reusable auxiliary functions

const apply = f => a => f(a);

const flip = f => b => a => f(a) (b);

const uncurry = f => (a, b) => f(a) (b);

const push = x => xs => (xs.push(x), xs);

const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);

const some = f => xs => xs.some(apply(f));


// the actual de-duplicate function

const uniqueBy = f => foldl(
   acc => x => some(f(x)) (acc)
    ? acc
    : push(x) (acc)
 ) ([]);


// comparators

const eq = y => x => x === y;

// string equality case insensitive :D
const seqCI = y => x => x.toLowerCase() === y.toLowerCase();


// mock data

const xs = [1,2,3,1,2,3,4];

const ys = ["a", "b", "c", "A", "B", "C", "D"];


console.log( uniqueBy(eq) (xs) );

console.log( uniqueBy(seqCI) (ys) );

We can easily derive unique from unqiueBy or use the faster implementation utilizing Sets:

const unqiue = uniqueBy(eq);

// const unique = xs => Array.from(new Set(xs));

Benefits of this approach:

generic solution by using a separate comparator function
declarative and succinct implementation
reuse of other small, generic functions

Performance Considerations

uniqueBy isn't as fast as an imperative implementation with loops, but it is way more expressive due to its genericity.

If you identify uniqueBy as the cause of a concrete performance penalty in your app, replace it with optimized code. That is, write your code first in an functional, declarative way. Afterwards, provided that you encounter performance issues, try to optimize the code at the locations, which are the cause of the problem.

Memory Consumption and Garbage Collection

uniqueBy utilizes mutations (push(x) (acc)) hidden inside its body. It reuses the accumulator instead of throwing it away after each iteration. This reduces memory consumption and GC pressure. Since this side effect is wrapped inside the function, everything outside remains pure.

Upvotes: 6

ivoputzer

Reputation: 6469

The most concise way to remove duplicates from an array using native javascript functions is to use a sequence like below:

vals.sort().reduce(function(a, b){ if (b != a[0]) a.unshift(b); return a }, [])

there's no need for slice nor indexOf within the reduce function, like i've seen in other examples! it makes sense to use it along with a filter function though:

vals.filter(function(v, i, a){ return i == a.indexOf(v) })

Yet another ES6(2015) way of doing this that already works on a few browsers is:

Array.from(new Set(vals))

or even using the spread operator:

[...new Set(vals)]

cheers!

Upvotes: 38