25

I have an array of objects

list = [{x:1,y:2}, {x:3,y:4}, {x:5,y:6}, {x:1,y:2}]

And I'm looking for an efficient way (if possible O(log(n))) to remove duplicates and to end up with

list = [{x:1,y:2}, {x:3,y:4}, {x:5,y:6}]

I've tried _.uniq or even _.contains but couldn't find a satisfying solution.

Thanks!

Edit : The question has been identified as a duplicate of another one. I saw this question before posting but it didn't answer my question since it's an array of object (and not a 2-dim array, thanks Aaron), or at least the solutions on the other question weren't working in my case.

15

Vanilla JS version:

const list = [{x:1,y:2}, {x:3,y:4}, {x:5,y:6}, {x:1,y:2}];

function dedupe(arr) {
  return arr.reduce(function(p, c) {

    // create an identifying id from the object values
    var id = [c.x, c.y].join('|');

    // if the id is not found in the temp array
    // add the object to the output array
    // and add the key to the temp array
    if (p.temp.indexOf(id) === -1) {
      p.out.push(c);
      p.temp.push(id);
    }
    return p;

    // return the deduped array
  }, {
    temp: [],
    out: []
  }).out;
}

console.log(dedupe(list));

|improve this answer|||||
29

Plain javascript (ES2015), using Set

const list = [{ x: 1, y: 2 }, { x: 3, y: 4 }, { x: 5, y: 6 }, { x: 1, y: 2 }];

const uniq = new Set(list.map(e => JSON.stringify(e)));

const res = Array.from(uniq).map(e => JSON.parse(e));

document.write(JSON.stringify(res));

|improve this answer|||||
  • 4
    stringify and parse don't look like the most performant way to achieve this. – calbertts Aug 14 '17 at 14:18
  • 6
    You shouldn't be using var when writing code in ES2015! – Amin Jafari Oct 4 '17 at 19:12
19

Try using the following:

list = list.filter((elem, index, self) => self.findIndex(
    (t) => {return (t.x === elem.x && t.y === elem.y)}) === index)
|improve this answer|||||
7

I would use a combination of Arrayr.prototype.reduce and Arrayr.prototype.some methods with spread operator.

1. Explicit solution. Based on complete knowledge of the array object contains.

list = list.reduce((r, i) => 
  !r.some(j => i.x === j.x && i.y === j.y) ? [...r, i] : r
, [])

Here we have strict limitation on compared objects structure: {x: N, y: M}. And [{x:1, y:2}, {x:1, y:2, z:3}] will be filtered to [{x:1, y:2}].

2. Generic solution, JSON.stringify(). The compared objects could have any number of any properties.

list = list.reduce((r, i) => 
  !r.some(j => JSON.stringify(i) === JSON.stringify(j)) ? [...r, i] : r
, [])

This approach has a limitation on properties order, so [{x:1, y:2}, {y:2, x:1}] won't be filtered.

3. Generic solution, Object.keys(). The order doesn't matter.

list = list.reduce((r, i) => 
  !r.some(j => !Object.keys(i).some(k => i[k] !== j[k])) ? [...r, i] : r
, [])

This approach has another limitation: compared objects must have the same list of keys. So [{x:1, y:2}, {x:1}] would be filtered despite the obvious difference.

4. Generic solution, Object.keys() + .length.

list = list.reduce((r, i) => 
  !r.some(j => Object.keys(i).length === Object.keys(j).length 
    && !Object.keys(i).some(k => i[k] !== j[k])) ? [...r, i] : r
, [])

With the last approach objects are being compared by the number of keys, by keys itself and by key values.

I created a Plunker to play with it.

|improve this answer|||||
4

Filter the array after checking if already in a temorary object in O(n).

var list = [{ x: 1, y: 2 }, { x: 3, y: 4 }, { x: 5, y: 6 }, { x: 1, y: 2 }],
    filtered = function (array) {
        var o = {};
        return array.filter(function (a) {
            var k = a.x + '|' + a.y;
            if (!o[k]) {
                o[k] = true;
                return true;
            }
        });
    }(list);

document.write('<pre>' + JSON.stringify(filtered, 0, 4) + '</pre>');

|improve this answer|||||
2

The following will work:

var a = [{x:1,y:2}, {x:3,y:4}, {x:5,y:6}, {x:1,y:2}];

var b = _.uniq(a, function(v) { 
    return v.x && v.y;
})

console.log(b);  // [ { x: 1, y: 2 }, { x: 3, y: 4 }, { x: 5, y: 6 } ]
|improve this answer|||||
  • 1
    Thanks! Works for me, is it faster than Andy's solution ? – kwn Mar 16 '16 at 10:10
  • 2
    Unless you're dealing with 10s of 1000s of elements, performance shouldn't be an issue. I guess you have to weigh up the cost of loading a separate library (if lodash isn't in your stack already) or just using a slightly more verbose vanilla function. – Andy Mar 16 '16 at 10:18
  • 1
    That's what I wanted to add, too :-) @Andy – baao Mar 16 '16 at 10:19
  • 1
    Don't think this works properly e.g. 1 && 2 == 2 && 2 – Gruff Bunny Mar 16 '16 at 10:48
  • 1
    If the input was [{x:1, y: 2}, {x: 2. y:2}] then the result would be [{x:1, y:2}] - the second object would be removed even though it's not a duplicate – Gruff Bunny Mar 16 '16 at 10:57
0

One liners for ES6+

If you want to find uniq by x and y:

arr.filter((v,i,a)=>a.findIndex(t=>(t.x === v.x && t.y===v.y))===i)

If you want to find uniques by all properties:

arr.filter((v,i,a)=>a.findIndex(t=>(JSON.stringify(t) === JSON.stringify(v)))===i)
|improve this answer|||||
0

Using lodash you can use this one-liner:

 _.uniqBy(list, e => { return e.x && e.y })
|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.