Removing equivalent but unique objects from a Javascript array

Question

I have an array of objects similar to the following:

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

These objects represent the start and end point of lines and as such, {start: 1, end: 2} and {start: 2, end: 1} represent the same line.

I am trying to remove all duplicate lines from the array and cannot find an efficient or elegant way to do it. I have tried a nested loop but, I've been told that is bad practice (and I'm getting errors with my implementation, and it's just ugly).

for(var i = 0, numRoutes = routeArr.length; i < numRoutes; i++) {
    var primaryRoute = routeArr[i];

    for(var j = 0; j < numRoutes; j++) {
        var secondRoute = routeArr[j];

        if(primaryRoute.start === secondRoute.end && primaryRoute.end === secondRoute.start) {
            routeArr.splice(j, 1);
            continue;
        }
    }
}

Can anyone offer suggestions?

Answer 1

Create an object/map in javascript and keep the indexes of the unique objects, store "min(start,end):max(start,end)" as a key and index as a value. Here is an implementation of your question in javascript:

// your initial array
var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
];

// map where we will store key => value where key is a joined start,end of your array's item and value is an item index 
var keyToRouteIndexMap = {};

for (var i in routeArr){
    // calculating min and max from start and end to understand {start:1, end:2} and {start:2, end:1} object as duplicates
    var min = Math.min(routeArr[i].start,routeArr[i].end);
    var max = Math.max(routeArr[i].start,routeArr[i].end);
    // unique key 
    var key = min+':'+max;
    if (!keyToRouteIndexMap.hasOwnProperty(key)){
        keyToRouteIndexMap[key] = i;
    }
}

for(var key in keyToRouteIndexMap){
    if(keyToRouteIndexMap.hasOwnProperty(key)){
        console.log(routeArr[keyToRouteIndexMap[key]]);
    }
}

Answer 2

You can do like this. I guess this is very fast since there are no searches at all. One Array.prototype.reduce() operation to construct both the hash table (lookup table) and the reduced object at the same time. Then mapping the object keys to get the result. Here it is;

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
],

reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) && (p[c.start+"-"+c.end] = c);
                                     return p;},{}),
 result = Object.keys(reduced).map(e => reduced[e]);
console.log(result);

Well giving it a second thought i eliminated the redundant Object.keys() portion. Now this is nothing more than a single Array.prototype.reduce() pass all completed in just O(n). I suppose this might be as far as it gets concerning the performance. Check it out.

var routeArr = [
    {start: 1, end: 2},
    {start: 1, end: 3},
    {start: 1, end: 4},
    {start: 2, end: 1},
    {start: 3, end: 1},
    {start: 4, end: 1}
],

     reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end]  ||
                                           p[c.end+"-"+c.start]) &&
                                          (p[c.start+"-"+c.end] = true,
                                           p.result.push(c));
                                           return p;
                                        },{"result":[]});
console.log(reduced.result);

Well ok yes i have to agree it looks a little cryptic but it is very simple.

• We are using Array.prototype.reduce() method with an initial value here. This is our initial value {"result":[]}. When reducing our routeArr array our initial element to start with is now an object with a single property named result and value of an empty array.
• reduce has been provided with an anonymous callback function which takes two arguments (p,c) p stands for previous and c stands for current. So in the first run p is our initializing object, i mean this {"result":[]} and c is the item at index 0 of the array (routeArr) that we have called reduce upon. So in the first round c is {start: 1, end: 2}.
• In the beginning of every round we check if our p object contains a property which represent the current elements values in both orders. So the check comes like this !(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) which in human terms means "is it true that you don't have a string property like c.start-c.end or c.end-c.start".. So for example in the first round the check is like "is it true that you don't have a string property like "1-2" or "2-1". If it has (false) we do nothing but if it hasn't we perform the following actions;
• && (p[c.start+"-"+c.end] = true, p.result.push(c)); return p;. OK the first && ties the two instructions in the parens to the condition of the previous instruction to evaluate to true. In a && b instruction JS engine will only evaluate b if a evaluates to true. So you got it. Again in human terms this is what happens. "is it true that you don't have a string property like "1-2" or "2-1" turns true and we create a property "1-2" with a value true. So in next rounds if we meet a 1-2 or 2-1 we will do nothing at all. Then we push this current object to the result property of the same object (p.result) to become a unique representative of all of it's duplicates or twins. Then we return p for a healthy continuation of the reduce cycles.

I hope it is clear.