53

I have two arrays list1 and list2 which have objects with some properties; userId is the Id or unique property:

list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
]

list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
]

I'm looking for an easy way to execute the following three operations:

  1. list1 operation list2 should return the intersection of elements:

    [
        { userId: 1235, userName: 'ABC'  },
        { userId: 1236, userName: 'IJKL' }
    ]
    
  2. list1 operation list2 should return the list of all elements from list1 which don't occur in list2:

    [
        { userId: 1234, userName: 'XYZ'  },
        { userId: 1237, userName: 'WXYZ' }, 
        { userId: 1238, userName: 'LMNO' }
    ]
    
  3. list2 operation list1 should return the list of elements from list2 which don't occur in list1:

    [
        { userId: 1252, userName: 'AAAA' }
    ]
    
3
  • 1
    Your title says "difference" but your question mentions "intersection". Which is it? Can you give an example on what you'd expect the output to be?
    – Mr. Llama
    Oct 26, 2015 at 22:10
  • 2
    lodash.com/docs#intersection Oct 26, 2015 at 22:13
  • @MikeRobinson using lodash didn't work for me, as it didn't compare the objects correctly
    – lumos42
    Mar 31, 2022 at 13:30

8 Answers 8

59

You could define three functions inBoth, inFirstOnly, and inSecondOnly which all take two lists as arguments, and return a list as can be understood from the function name. The main logic could be put in a common function operation that all three rely on.

Here are a few implementations for that operation to choose from, for which you can find a snippet further down:

  • Plain old JavaScript for loops
  • Arrow functions using filter and some array methods
  • Optimised lookup with a Set

Plain old for loops

// Generic helper function that can be used for the three operations:        
function operation(list1, list2, isUnion) {
    var result = [];
    
    for (var i = 0; i < list1.length; i++) {
        var item1 = list1[i],
            found = false;
        for (var j = 0; j < list2.length && !found; j++) {
            found = item1.userId === list2[j].userId;
        }
        if (found === !!isUnion) { // isUnion is coerced to boolean
            result.push(item1);
        }
    }
    return result;
}

// Following functions are to be used:
function inBoth(list1, list2) {
    return operation(list1, list2, true);
}

function inFirstOnly(list1, list2) {
    return operation(list1, list2);
}

function inSecondOnly(list1, list2) {
    return inFirstOnly(list2, list1);
}

// Sample data
var list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
];
var list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
];
  
console.log('inBoth:', inBoth(list1, list2)); 
console.log('inFirstOnly:', inFirstOnly(list1, list2)); 
console.log('inSecondOnly:', inSecondOnly(list1, list2)); 

Arrow functions using filter and some array methods

This uses some ES5 and ES6 features:

// Generic helper function that can be used for the three operations:        
const operation = (list1, list2, isUnion = false) =>
    list1.filter( a => isUnion === list2.some( b => a.userId === b.userId ) );

// Following functions are to be used:
const inBoth = (list1, list2) => operation(list1, list2, true),
      inFirstOnly = operation,
      inSecondOnly = (list1, list2) => inFirstOnly(list2, list1);

// Sample data
const list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
];
const list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
];
  
console.log('inBoth:', inBoth(list1, list2)); 
console.log('inFirstOnly:', inFirstOnly(list1, list2)); 
console.log('inSecondOnly:', inSecondOnly(list1, list2));

Optimising lookup

The above solutions have a O(n²) time complexity because of the nested loop -- some represents a loop as well. So for large arrays you'd better create a (temporary) hash on user-id. This can be done on-the-fly by providing a Set (ES6) as argument to a function that will generate the filter callback function. That function can then perform the look-up in constant time with has:

// Generic helper function that can be used for the three operations:        
const operation = (list1, list2, isUnion = false) =>
    list1.filter(
        (set => a => isUnion === set.has(a.userId))(new Set(list2.map(b => b.userId)))
    );

// Following functions are to be used:
const inBoth = (list1, list2) => operation(list1, list2, true),
      inFirstOnly = operation,
      inSecondOnly = (list1, list2) => inFirstOnly(list2, list1);

// Sample data
const list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
];
const list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
];
  
console.log('inBoth:', inBoth(list1, list2)); 
console.log('inFirstOnly:', inFirstOnly(list1, list2)); 
console.log('inSecondOnly:', inSecondOnly(list1, list2));

1
  • 1
    Soooo many moving parts in the "Optimising Lookup" section. Well done and thanks.
    – monsto
    Aug 29 at 21:04
42

short answer:

list1.filter(a => list2.some(b => a.userId === b.userId));  
list1.filter(a => !list2.some(b => a.userId === b.userId));  
list2.filter(a => !list1.some(b => a.userId === b.userId));  

longer answer:
The code above will check objects by userId value,
if you need complex compare rules, you can define custom comparator:

comparator = function (a, b) {
    return a.userId === b.userId && a.userName === b.userName
};  
list1.filter(a => list2.some(b => comparator(a, b)));
list1.filter(a => !list2.some(b => comparator(a, b)));
list2.filter(a => !list1.some(b => comparator(a, b)));

Also there is a way to compare objects by references
WARNING! two objects with same values will be considered different:

o1 = {"userId":1};
o2 = {"userId":2};
o1_copy = {"userId":1};
o1_ref = o1;
[o1].filter(a => [o2].includes(a)).length; // 0
[o1].filter(a => [o1_copy].includes(a)).length; // 0
[o1].filter(a => [o1_ref].includes(a)).length; // 1
1
14

Just use filter and some array methods of JS and you can do that.

let arr1 = list1.filter(e => {
   return !list2.some(item => item.userId === e.userId);
});

This will return the items that are present in list1 but not in list2. If you are looking for the common items in both lists. Just do this.

let arr1 = list1.filter(e => {
   return list2.some(item => item.userId === e.userId); // take the ! out and you're done
});
4

Use lodash's _.isEqual method. Specifically:

list1.reduce(function(prev, curr){
  !list2.some(function(obj){
    return _.isEqual(obj, curr)
  }) ? prev.push(curr): false;
  return prev
}, []);

Above gives you the equivalent of A given !B (in SQL terms, A LEFT OUTER JOIN B). You can move the code around the code to get what you want!

1
function intersect(first, second) {
    return intersectInternal(first, second, function(e){ return e });
}

function unintersect(first, second){
    return intersectInternal(first, second, function(e){ return !e });  
}

function intersectInternal(first, second, filter) {
    var map = {};

    first.forEach(function(user) { map[user.userId] = user; });

    return second.filter(function(user){ return filter(map[user.userId]); })
}
0

Here is a functionnal programming solution with underscore/lodash to answer your first question (intersection).

list1 = [ {userId:1234,userName:'XYZ'}, 
          {userId:1235,userName:'ABC'}, 
          {userId:1236,userName:'IJKL'},
          {userId:1237,userName:'WXYZ'}, 
          {userId:1238,userName:'LMNO'}
        ];

list2 = [ {userId:1235,userName:'ABC'},  
          {userId:1236,userName:'IJKL'},
          {userId:1252,userName:'AAAA'}
        ];

_.reduce(list1, function (memo, item) {
        var same = _.findWhere(list2, item);
        if (same && _.keys(same).length === _.keys(item).length) {
            memo.push(item);
        }
        return memo
    }, []);

I'll let you improve this to answer the other questions ;-)

1
  • 1
    NB: In true functional programming style there would be no push (which mutates the array)
    – trincot
    Oct 24, 2018 at 6:08
0

This is the solution that worked for me.

 var intersect = function (arr1, arr2) {
            var intersect = [];
            _.each(arr1, function (a) {
                _.each(arr2, function (b) {
                    if (compare(a, b))
                        intersect.push(a);
                });
            });

            return intersect;
        };

 var unintersect = function (arr1, arr2) {
            var unintersect = [];
            _.each(arr1, function (a) {
                var found = false;
                _.each(arr2, function (b) {
                    if (compare(a, b)) {
                        found = true;    
                    }
                });

                if (!found) {
                    unintersect.push(a);
                }
            });

            return unintersect;
        };

        function compare(a, b) {
            if (a.userId === b.userId)
                return true;
            else return false;
        }
0

Typescript and more generic version of @trincot's answer

type Primative = string | number | boolean
type GetId<T> = (item: T) => Primative

const operation = <T, U, B extends boolean>(
  list1: T[],
  list2: U[],
  isUnion: B,
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): T[] =>
  list1.filter(
    (a) => isUnion === list2.some((b) => getList1Id(a) === getList2Id(b)),
  )

export const inBoth = <T, U>(
  list1: T[],
  list2: U[],
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): T[] => operation(list1, list2, true, getList1Id, getList2Id)

export const inFirstOnly = <T, U>(
  list1: T[],
  list2: U[],
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): T[] => operation(list1, list2, false, getList1Id, getList2Id)

export const inSecondOnly = <T, U>(
  list1: T[],
  list2: U[],
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): U[] => operation(list2, list1, false, getList2Id, getList1Id)

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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