Is there a way to return the difference between two arrays in JavaScript?
For example:
var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];
// need ["c", "d"]
Array.prototype.filter() and Array.prototype.includes() come in handy here.
let intersection = arr1.filter(x => arr2.includes(x));
Yields values which are present in both A and B.
let A, B, intersection;
A = [1, 2, 3];
B = [2, 3];
intersection = A.filter(x => B.includes(x));
console.log(intersection);
A = [1, 2, 3];
B = [2, 3, 5];
intersection = A.filter(x => B.includes(x));
console.log(intersection);
// both operations return [2, 3]
(Values in just A.)
let difference = arr1.filter(x => !arr2.includes(x));
Yields values that are present in just A.
let A, B, intersection;
A = [1, 2, 3];
B = [2, 3];
intersection = A.filter(x => !B.includes(x));
console.log(intersection);
A = [1, 2, 3];
B = [2, 3, 5];
intersection = A.filter(x => !B.includes(x));
console.log(intersection);
// both operations return [1]
let symDifference = arr1.filter(x => !arr2.includes(x))
.concat(arr2.filter(x => !arr1.includes(x)));
Yields values that are only in A or B, but not both ("exclusive or").
This is what you get if you take the difference of both arrays with each other, and combine the two results (You get an array containing all the elements of A that are not in B and vice-versa).
let A, B, intersection;
A = [1, 2, 3];
B = [2, 3];
intersection = A.filter(x => !B.includes(x))
.concat(B.filter(x => !A.includes(x)));
console.log(intersection);
// returns [1]
A = [1, 2, 3];
B = [2, 3, 5];
intersection = A.filter(x => !B.includes(x))
.concat(B.filter(x => !A.includes(x)));
console.log(intersection);
// returns [1, 5]
See the answer by @Joshaven Potter, for an example of how you can use these functions directly on arrays.
Set, values have to be unique, no?[1,2,3] [2,3,5] given that the numbers are unique but if you had say [1,1,2,3] [1,2,3,5] and expected [1] you couldn't use Set. Your solution wouldn't work either though :-/ I ended up creating this function because I couldn't figure out a satisfactory way to do it more succinctly. If you have any ideas on how to do that, I'd love to know!includes, which obviously gave massive speed increases (improved the complexity from O(n^2) to O(n log2 n)). Using her little function instead of binary search came out 2-3x times faster, especially when the arrays were almost the same. 10x+ when using crazy arrays (100,000,000 elements)...Array.prototype.diff = function(a) {
return this.filter(function(i) {return a.indexOf(i) < 0;});
};
//////////////
// Examples //
//////////////
const dif1 = [1,2,3,4,5,6].diff( [3,4,5] );
console.log(dif1); // => [1, 2, 6]
const dif2 = ["test1", "test2","test3","test4","test5","test6"].diff(["test1","test2","test3","test4"]);
console.log(dif2); // => ["test5", "test6"]
Note .indexOf() and .filter() are not available before IE9.
[1,2,3].diff([3,4,5]) it will return [1,2] instead of [1,2,4,5] so it doesn't solve the problem in the original question, something to be aware of.This answer was written in 2009, so it is a bit outdated, also it's rather educational for understanding the problem. Best solution I'd use today would be
let difference = arr1.filter(x => !arr2.includes(x));
(credits to other author here)
I assume you are comparing a normal array. If not, you need to change the for loop to a for .. in loop.
function arr_diff (a1, a2) {
var a = [], diff = [];
for (var i = 0; i < a1.length; i++) {
a[a1[i]] = true;
}
for (var i = 0; i < a2.length; i++) {
if (a[a2[i]]) {
delete a[a2[i]];
} else {
a[a2[i]] = true;
}
}
for (var k in a) {
diff.push(k);
}
return diff;
}
console.log(arr_diff(['a', 'b'], ['a', 'b', 'c', 'd']));
console.log(arr_diff("abcd", "abcde"));
console.log(arr_diff("zxc", "zxc"));
var a1 = ['a', 'b']; and var a2 = ['a', 'b', 'c', 'd', 'b'];, it will return wrong answer, i.e. ['c', 'd', 'b'] instead of ['c', 'd'].function diff2(a, b) { var i, la = a.length, lb = b.length, res = []; if (!la) return b; else if (!lb) return a; for (i = 0; i < la; i++) { if (b.indexOf(a[i]) === -1) res.push(a[i]); } for (i = 0; i < lb; i++) { if (a.indexOf(b[i]) === -1) res.push(b[i]); } return res; }This is by far the easiest way to get exactly the result you are looking for, using jQuery:
var diff = $(old_array).not(new_array).get();
diff now contains what was in old_array that is not in new_array
.not with an array, jQuery uses it's built-in utility .grep() which is specifically for filtering arrays. I can't see this changing.The difference method in Underscore (or its drop-in replacement, Lo-Dash) can do this too:
(R)eturns the values from array that are not present in the other arrays
_.difference([1, 2, 3, 4, 5], [5, 2, 10]);
=> [1, 3, 4]
As with any Underscore function, you could also use it in a more object-oriented style:
_([1, 2, 3, 4, 5]).difference([5, 2, 10]);
There are two possible intepretations for "difference". I'll let you choose which one you want. Say you have:
const arr1 = ['a', 'b' ];
const arr2 = [ 'b', 'c'];
If you want to get ['a'] (everything in arr1, minus what's in arr2), use this function:
function difference(arr1, arr2) {
const set2 = new Set(arr2);
return arr1.filter(item => !set2.has(item));
};
If you want to get ['a', 'c'] (all elements contained in either arr1 or arr2, but not both -- the so-called symmetric difference), use this function:
function symmetricDifference(arr1, arr2) {
const set1 = new Set(arr1);
const set2 = new Set(arr2);
const onlyInArr1 = arr1.filter(item => !set2.has(item));
const onlyInArr2 = arr2.filter(item => !set1.has(item));
return [...onlyInArr1, ...onlyInArr2];
}
If you are using lodash, you can use _.difference(arr1, arr2) (case 1 above) or _.xor(arr1, arr2) (case 2).
If you are using Underscore.js, you can use the _.difference(arr1, arr2) function for case 1.
If arr1 contains no duplicates (or you don't mind having duplicates removed), you can take advantage of the new (widely-available as of 2024) set.difference() and set.symmetricDifference() methods:
const difference = [...new Set(arr1).difference(new Set(arr2))];
const symmetricDifference = [...new Set(arr1).symmetricDifference(new Set(arr2))];
Note: One might think that turning a Set back into an array could mess up the order of elements, but luckily the ECMAScript specification requires Set objects to preserve insertion order.
Set to solve this problem is amazing.A cleaner approach in ES6 is the following solution.
var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];
a2.filter(d => !a1.includes(d)) // gives ["c", "d"]
a2.filter(d => a1.includes(d)) // gives ["a", "b"]
[ ...a2.filter(d => !a1.includes(d)),
...a1.filter(d => !a2.includes(d)) ]
a1 = ['a', 'b', 'e'] : e won't be extracted.To get the symmetric difference you need to compare the arrays in both ways (or in all the ways in case of multiple arrays)
// diff between just two arrays:
function arrayDiff(a, b) {
return [
...a.filter(x => !b.includes(x)),
...b.filter(x => !a.includes(x))
];
}
// diff between multiple arrays:
function arrayDiff(...arrays) {
return [].concat(...arrays.map( (arr, i) => {
const others = arrays.slice(0);
others.splice(i, 1);
const unique = [...new Set([].concat(...others))];
return arr.filter(x => !unique.includes(x));
}));
}
// diff between just two arrays:
function arrayDiff(a, b) {
return [
...a.filter(x => b.indexOf(x) === -1),
...b.filter(x => a.indexOf(x) === -1)
];
}
// diff between multiple arrays:
function arrayDiff(...arrays) {
return [].concat(...arrays.map( (arr, i) => {
const others = arrays.slice(0);
others.splice(i, 1);
const unique = [...new Set([].concat(...others))];
return arr.filter(x => unique.indexOf(x) === -1);
}));
}
// diff between just two arrays:
function arrayDiff(a, b) {
var arrays = Array.prototype.slice.call(arguments);
var diff = [];
arrays.forEach(function(arr, i) {
var other = i === 1 ? a : b;
arr.forEach(function(x) {
if (other.indexOf(x) === -1) {
diff.push(x);
}
});
})
return diff;
}
// diff between multiple arrays:
function arrayDiff() {
var arrays = Array.prototype.slice.call(arguments);
var diff = [];
arrays.forEach(function(arr, i) {
var others = arrays.slice(0);
others.splice(i, 1);
var otherValues = Array.prototype.concat.apply([], others);
var unique = otherValues.filter(function (x, j) {
return otherValues.indexOf(x) === j;
});
diff = diff.concat(arr.filter(x => unique.indexOf(x) === -1));
});
return diff;
}
Example:
// diff between two arrays:
const a = ['a', 'd', 'e'];
const b = ['a', 'b', 'c', 'd'];
arrayDiff(a, b); // (3) ["e", "b", "c"]
// diff between multiple arrays
const a = ['b', 'c', 'd', 'e', 'g'];
const b = ['a', 'b'];
const c = ['a', 'e', 'f'];
arrayDiff(a, b, c); // (4) ["c", "d", "g", "f"]
function arrayDiffByKey(key, ...arrays) {
return [].concat(...arrays.map( (arr, i) => {
const others = arrays.slice(0);
others.splice(i, 1);
const unique = [...new Set([].concat(...others))];
return arr.filter( x =>
!unique.some(y => x[key] === y[key])
);
}));
}
Example:
const a = [{k:1}, {k:2}, {k:3}];
const b = [{k:1}, {k:4}, {k:5}, {k:6}];
const c = [{k:3}, {k:5}, {k:7}];
arrayDiffByKey('k', a, b, c); // (4) [{k:2}, {k:4}, {k:6}, {k:7}]
You could use a Set in this case. It is optimized for this kind of operation (union, intersection, difference).
Make sure it applies to your case, once it allows no duplicates.
var a = new JS.Set([1,2,3,4,5,6,7,8,9]);
var b = new JS.Set([2,4,6,8]);
a.difference(b)
// -> Set{1,3,5,7,9}
Set function without having to get everything else...difference method.const unique = (a) => [...new Set(a)];
const uniqueBy = (x,f)=>Object.values(x.reduce((a,b)=>((a[f(b)]=b),a),{}));
const intersection = (a, b) => a.filter((v) => b.includes(v));
const diff = (a, b) => a.filter((v) => !b.includes(v));
const symDiff = (a, b) => diff(a, b).concat(diff(b, a));
const union = (a, b) => diff(a, b).concat(b);
const a = unique([1, 2, 3, 4, 5, 5]);
console.log(a);
const b = [4, 5, 6, 7, 8];
console.log(intersection(a, b), diff(a, b), symDiff(a, b), union(a, b));
console.log(uniqueBy(
[
{ id: 1, name: "abc" },
{ id: 2, name: "xyz" },
{ id: 1, name: "abc" },
],
(v) => v.id
));
const intersectionBy = (a, b, f) => a.filter((v) => b.some((u) => f(v, u)));
console.log(intersectionBy(
[
{ id: 1, name: "abc" },
{ id: 2, name: "xyz" },
],
[
{ id: 1, name: "abc" },
{ id: 3, name: "pqr" },
],
(v, u) => v.id === u.id
));
const diffBy = (a, b, f) => a.filter((v) => !b.some((u) => f(v, u)));
console.log(diffBy(
[
{ id: 1, name: "abc" },
{ id: 2, name: "xyz" },
],
[
{ id: 1, name: "abc" },
{ id: 3, name: "pqr" },
],
(v, u) => v.id === u.id
));
const unique = <T>(array: T[]) => [...new Set(array)];
const intersection = <T>(array1: T[], array2: T[]) =>
array1.filter((v) => array2.includes(v));
const diff = <T>(array1: T[], array2: T[]) =>
array1.filter((v) => !array2.includes(v));
const symDiff = <T>(array1: T[], array2: T[]) =>
diff(array1, array2).concat(diff(array2, array1));
const union = <T>(array1: T[], array2: T[]) =>
diff(array1, array2).concat(array2);
const intersectionBy = <T>(
array1: T[],
array2: T[],
predicate: (array1Value: T, array2Value: T) => boolean
) => array1.filter((v) => array2.some((u) => predicate(v, u)));
const diffBy = <T>(
array1: T[],
array2: T[],
predicate: (array1Value: T, array2Value: T) => boolean
) => array1.filter((v) => !array2.some((u) => predicate(v, u)));
const uniqueBy = <T>(
array: T[],
predicate: (v: T, i: number, a: T[]) => string
) =>
Object.values(
array.reduce((acc, value, index) => {
acc[predicate(value, index, array)] = value;
return acc;
}, {} as { [key: string]: T })
);
function diff(a1, a2) {
return a1.concat(a2).filter(function(val, index, arr){
return arr.indexOf(val) === arr.lastIndexOf(val);
});
}
Merge both the arrays, unique values will appear only once so indexOf() will be the same as lastIndexOf().
With the arrival of ES6 with sets and splat operator (at the time of being works only in Firefox, check compatibility table), you can write the following one liner:
var a = ['a', 'b', 'c', 'd'];
var b = ['a', 'b'];
var b1 = new Set(b);
var difference = [...new Set(a.filter(x => !b1.has(x)))];
which will result in [ "c", "d" ].
b.filter(x => !a.indexOf(x)))O(n + m) your solution is O(n * m) where n and m are lengths of arrays. Take long lists and my solution will run in seconds, while yours will take hours.a.filter(x => !b1.has(x)) is simpler. And note the spec only requires the complexity to be n * f(m) + m with f(m) sublinear on average. It's better than n * m, but not necessarily n + m.var difference = [...new Set([...a].filter(x => !b1.has(x)))]; Why are you creating duplicate 'a' array? Why are you turning result of filter into a set and then back into array? Isn't this equivalent to var difference = a.filter(x => !b1.has(x));to subtract one array from another, simply use the snippet below:
var a1 = ['1','2','3','4','6'];
var a2 = ['3','4','5'];
var items = new Array();
items = jQuery.grep(a1,function (item) {
return jQuery.inArray(item, a2) < 0;
});
It will returns ['1,'2','6'] that are items of first array which don't exist in the second.
Therefore, according to your problem sample, following code is the exact solution:
var array1 = ["test1", "test2","test3", "test4"];
var array2 = ["test1", "test2","test3","test4", "test5", "test6"];
var _array = new Array();
_array = jQuery.grep(array2, function (item) {
return jQuery.inArray(item, array1) < 0;
});
Another way to solve the problem
function diffArray(arr1, arr2) {
return arr1.concat(arr2).filter(function (val) {
if (!(arr1.includes(val) && arr2.includes(val)))
return val;
});
}
diffArray([1, 2, 3, 7], [3, 2, 1, 4, 5]); // return [7, 4, 5]
Also, you can use arrow function syntax:
const diffArray = (arr1, arr2) => arr1.concat(arr2)
.filter(val => !(arr1.includes(val) && arr2.includes(val)));
diffArray([1, 2, 3, 7], [3, 2, 1, 4, 5]); // return [7, 4, 5]
Computing the difference between two arrays is one of the Set operations. The term already indicates that the native Set type should be used, in order to increase the lookup speed. Anyway, there are three permutations when you compute the difference between two sets:
[+left difference] [-intersection] [-right difference]
[-left difference] [-intersection] [+right difference]
[+left difference] [-intersection] [+right difference]
Here is a functional solution that reflects these permutations.
difference:// small, reusable auxiliary functions
const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
// left difference
const differencel = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? false
: true
) (xs);
};
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run the computation
console.log( differencel(xs) (ys) );
difference:differencer is trivial. It is just differencel with flipped arguments. You can write a function for convenience: const differencer = flip(differencel). That's all!
difference:Now that we have the left and right one, implementing the symmetric difference gets trivial as well:
// small, reusable auxiliary functions
const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const concat = y => xs => xs.concat(y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
// left difference
const differencel = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? false
: true
) (xs);
};
// symmetric difference
const difference = ys => xs =>
concat(differencel(xs) (ys)) (flip(differencel) (xs) (ys));
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run the computation
console.log( difference(xs) (ys) );
I guess this example is a good starting point to obtain an impression what functional programming means:
Programming with building blocks that can be plugged together in many different ways.
A solution using indexOf() will be ok for small arrays but as they grow in length the performance of the algorithm approaches O(n^2). Here's a solution that will perform better for very large arrays by using objects as associative arrays to store the array entries as keys; it also eliminates duplicate entries automatically but only works with string values (or values which can be safely stored as strings):
function arrayDiff(a1, a2) {
var o1={}, o2={}, diff=[], i, len, k;
for (i=0, len=a1.length; i<len; i++) { o1[a1[i]] = true; }
for (i=0, len=a2.length; i<len; i++) { o2[a2[i]] = true; }
for (k in o1) { if (!(k in o2)) { diff.push(k); } }
for (k in o2) { if (!(k in o1)) { diff.push(k); } }
return diff;
}
var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];
arrayDiff(a1, a2); // => ['c', 'd']
arrayDiff(a2, a1); // => ['c', 'd']
The above answer by Joshaven Potter is great. But it returns elements in array B that are not in array C, but not the other way around. For example, if var a=[1,2,3,4,5,6].diff( [3,4,5,7]); then it will output: ==> [1,2,6], but not [1,2,6,7], which is the actual difference between the two. You can still use Potter's code above but simply redo the comparison once backwards too:
Array.prototype.diff = function(a) {
return this.filter(function(i) {return !(a.indexOf(i) > -1);});
};
////////////////////
// Examples
////////////////////
var a=[1,2,3,4,5,6].diff( [3,4,5,7]);
var b=[3,4,5,7].diff([1,2,3,4,5,6]);
var c=a.concat(b);
console.log(c);
This should output: [ 1, 2, 6, 7 ]
Very Simple Solution with the filter function of JavaScript:
var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];
function diffArray(arr1, arr2) {
var newArr = [];
var myArr = arr1.concat(arr2);
newArr = myArr.filter(function(item){
return arr2.indexOf(item) < 0 || arr1.indexOf(item) < 0;
});
alert(newArr);
}
diffArray(a1, a2);
If you have two list of objects
const people = [{name: 'cesar', age: 23}]
const morePeople = [{name: 'cesar', age: 23}, {name: 'kevin', age: 26}, {name: 'pedro', age: 25}]
let result2 = morePeople.filter(person => people.every(person2 => !person2.name.includes(person.name)))
Array.prototype.difference = function(e) {
return this.filter(function(i) {return e.indexOf(i) < 0;});
};
eg:-
[1,2,3,4,5,6,7].difference( [3,4,5] );
=> [1, 2, 6 , 7]
difference as function in a future version and this function then has a different function signature then yours, it will break your code or foreign libraries that use this function.How about this:
Array.prototype.contains = function(needle){
for (var i=0; i<this.length; i++)
if (this[i] == needle) return true;
return false;
}
Array.prototype.diff = function(compare) {
return this.filter(function(elem) {return !compare.contains(elem);})
}
var a = new Array(1,4,7, 9);
var b = new Array(4, 8, 7);
alert(a.diff(b));
So this way you can do array1.diff(array2) to get their difference (Horrible time complexity for the algorithm though - O(array1.length x array2.length) I believe)
const a1 = ['a', 'b', 'c', 'd'];
const a2 = ['a', 'b'];
const diffArr = a1.filter(o => !a2.includes(o));
console.log(diffArr);
Output:
[ 'c', 'd' ]
!a2.includes(o). I edited your answer if you don't mind...To find the difference of 2 arrays without duplicates:
function difference(arr1, arr2){
let setA = new Set(arr1);
let differenceSet = new Set(arr2.filter(ele => !setA.has(ele)));
return [...differenceSet ];
}
1.difference([2,2,3,4],[2,3,3,4]) will return []
2.difference([1,2,3],[4,5,6]) will return [4,5,6]
3.difference([1,2,3,4],[1,2]) will return []
4.difference([1,2],[1,2,3,4]) will return [3,4]
Note: The above solution requires that you always send the larger array as the second parameter. To find the absolute difference, you will need to first find the larger array of the two and then work on them.
To find the absolute difference of 2 arrays without duplicates:
function absDifference(arr1, arr2){
const {larger, smaller} = arr1.length > arr2.length ?
{larger: arr1, smaller: arr2} : {larger: arr2, smaller: arr1}
let setA = new Set(smaller);
let absDifferenceSet = new Set(larger.filter(ele => !setA.has(ele)));
return [...absDifferenceSet ];
}
1.absDifference([2,2,3,4],[2,3,3,4]) will return []
2.absDifference([1,2,3],[4,5,6]) will return [4,5,6]
3.absDifference([1,2,3,4],[1,2]) will return [3,4]
4.absDifference([1,2],[1,2,3,4]) will return [3,4]
Note the example 3 from both the solutions
Here is another solution that can return the differences, just like git diff: (it has been written in typescript, if you're not using typescript version, just remove the types)
/**
* util function to calculate the difference between two arrays (pay attention to 'from' and 'to'),
* it would return the mutations from 'from' to 'to'
* @param { T[] } from
* @param { T[] } to
* @returns { { [x in string]: boolean } } it would return the stringified version of array element, true means added,
* false means removed
*/
export function arrDiff<T>(from: T[], to: T[]): { [x in string]: boolean } {
var diff: { [x in string]: boolean } = {};
var newItems: T[] = []
diff = from.reduce((a, e) => ({ ...a, [JSON.stringify(e)]: true }), {})
for (var i = 0; i < to.length; i++) {
if (diff[JSON.stringify(to[i])]) {
delete diff[JSON.stringify(to[i])]
} else {
newItems.push(to[i])
}
}
return {
...Object.keys(diff).reduce((a, e) => ({ ...a, [e]: false }), {}),
...newItems.reduce((a, e) => ({ ...a, [JSON.stringify(e)]: true }), {})
}
}
Here is a sample of usage:
arrDiff(['a', 'b', 'c'], ['a', 'd', 'c', 'f']) //{"b": false, "d": true, "f": true}
Using http://phrogz.net/JS/ArraySetMath.js you can:
var array1 = ["test1", "test2","test3", "test4"];
var array2 = ["test1", "test2","test3","test4", "test5", "test6"];
var array3 = array2.subtract( array1 );
// ["test5", "test6"]
var array4 = array1.exclusion( array2 );
// ["test5", "test6"]
filter)fn callback parameter that lets you specify how to compare array itemsfunction diff(a, b, fn){
var max = Math.max(a.length, b.length);
d = [];
fn = typeof fn === 'function' ? fn : false
for(var i=0; i < max; i++){
var ac = i < a.length ? a[i] : undefined
bc = i < b.length ? b[i] : undefined;
for(var k=0; k < max; k++){
ac = ac === undefined || (k < b.length && (fn ? fn(ac, b[k]) : ac == b[k])) ? undefined : ac;
bc = bc === undefined || (k < a.length && (fn ? fn(bc, a[k]) : bc == a[k])) ? undefined : bc;
if(ac == undefined && bc == undefined) break;
}
ac !== undefined && d.push(ac);
bc !== undefined && d.push(bc);
}
return d;
}
alert(
"Test 1: " +
diff(
[1, 2, 3, 4],
[1, 4, 5, 6, 7]
).join(', ') +
"\nTest 2: " +
diff(
[{id:'a',toString:function(){return this.id}},{id:'b',toString:function(){return this.id}},{id:'c',toString:function(){return this.id}},{id:'d',toString:function(){return this.id}}],
[{id:'a',toString:function(){return this.id}},{id:'e',toString:function(){return this.id}},{id:'f',toString:function(){return this.id}},{id:'d',toString:function(){return this.id}}],
function(a, b){ return a.id == b.id; }
).join(', ')
);
length values. It's already plain property. jsperf.com/array-length-cachingI wanted a similar function which took in an old array and a new array and gave me an array of added items and an array of removed items, and I wanted it to be efficient (so no .contains!).
You can play with my proposed solution here: http://jsbin.com/osewu3/12.
Can anyone see any problems/improvements to that algorithm? Thanks!
Code listing:
function diff(o, n) {
// deal with empty lists
if (o == undefined) o = [];
if (n == undefined) n = [];
// sort both arrays (or this won't work)
o.sort(); n.sort();
// don't compare if either list is empty
if (o.length == 0 || n.length == 0) return {added: n, removed: o};
// declare temporary variables
var op = 0; var np = 0;
var a = []; var r = [];
// compare arrays and add to add or remove lists
while (op < o.length && np < n.length) {
if (o[op] < n[np]) {
// push to diff?
r.push(o[op]);
op++;
}
else if (o[op] > n[np]) {
// push to diff?
a.push(n[np]);
np++;
}
else {
op++;np++;
}
}
// add remaining items
if( np < n.length )
a = a.concat(n.slice(np, n.length));
if( op < o.length )
r = r.concat(o.slice(op, o.length));
return {added: a, removed: r};
}
var all over makes me feel a bit 🤮You can use underscore.js : http://underscorejs.org/#intersection
You have needed methods for array :
_.difference([1, 2, 3, 4, 5], [5, 2, 10]);
=> [1, 3, 4]
_.intersection([1, 2, 3], [101, 2, 1, 10], [2, 1]);
=> [1, 2]
This is working: basically merge the two arrays, look for the duplicates and push what is not duplicated into a new array which is the difference.
function diff(arr1, arr2) {
var newArr = [];
var arr = arr1.concat(arr2);
for (var i in arr){
var f = arr[i];
var t = 0;
for (j=0; j<arr.length; j++){
if(arr[j] === f){
t++;
}
}
if (t === 1){
newArr.push(f);
}
}
return newArr;
}
O(a1.length x log(a2.length))- is this performance possible in JavaScript?