109

I'm looking for a good algorithm to get all the elements in one array that are not elements in another array. So given these arrays:

var x = ["a","b","c","t"];
var ​​​​​​​​​y = [​​​​​​​"d","a","t","e","g"];

I want to end up with this array:

var z = ["d","e","g"];

I'm using jquery, so I can take advantage of $.each() and $.inArray(). Here's the solution I've come up with, but it seems like there should be a better way.

// goal is to get rid of values in y if they exist in x
var x = ["a","b","c","t"];
var y = ["d","a","t","e","g"];

var z = [];
$.each(y, function(idx, value){
  if ($.inArray(value,x) == -1) {
    z.push(value);
  }
});
​alert(z);  // should be ["d","e","g"]

Here is the code in action. Any ideas?

10 Answers 10

184

in ES6 simply

const a1 = ["a", "b", "c", "t"];
const a2 = ["d", "a", "t", "e", "g"];

console.log( a2.filter(x => !a1.includes(x)) );

(another option is a2.filter(x => a1.indexOf(x)===-1) )

0
77

Late answer with the new ECMA5 javascript:

var x = ["a","b","c","t"];
var y = ["d","a","t","e","g"];

myArray = y.filter( function( el ) {
  return x.indexOf( el ) < 0;
});
3
  • 3
    Any idea on the algorithmic complexity/scalability of this?
    – mikecsh
    Sep 3, 2015 at 16:55
  • @mikecsh Probably not good. Sorting both first and then marching through might be better.
    – ccook
    Mar 9, 2019 at 19:34
  • 1
    @ccook a proof of your statement may be useful actually. Otherwise is just a "Probably... maybe" sentence. Mar 21, 2019 at 15:05
18
var z = $.grep(y, function(el){return $.inArray(el, x) == -1}); 

Also, that method name is too short for its own good. I would expect it to mean isElementInArray, not indexOf.

For a demo with objects, see http://jsfiddle.net/xBDz3/6/

5
  • hmm, well my situation has objects in my arrays, not just simple strings. I put strings in my question to simplify things. I'm not sure your solution would work.
    – Tauren
    Jun 3, 2010 at 4:22
  • 1
    The name grep may be misleading. It doesn't really have anything to do with strings. It just takes a predicate. Other languages call the same thing filter. I made a demo. Jun 3, 2010 at 4:24
  • wow, after a quick test, it looks like that does work. The command grep is misleading, as I'm assuming it would work on text like the unix command. I'll do some more testing.
    – Tauren
    Jun 3, 2010 at 4:27
  • Note on current support of fiddle code: JSON.stringify(z) works in Chrome 55 where z.toSource() errors. Feb 17, 2017 at 22:45
  • ohh la la - very nice May 27, 2022 at 10:47
15

Here's an alternative using underscore.js:

function inAButNotInB(A, B) {
  return _.filter(A, function (a) {
    return !_.contains(B, a);
  });
}
1
  • 1
    I've moved away from being so dependent on jquery and am utilizing smaller libraries such as underscore and lodash. These libraries make solving problems like the original question so much easier. Thanks for including an underscore-based solution!
    – Tauren
    May 2, 2013 at 7:46
11

I am quite late now but maybe it will be helpful for someone.

If the array is not just a simple array but an array of objects then the following can be used:

var arr1 = [
    {
      "prop1": "value1",
      "prop2": "value2",
    },
    {
      "prop1": "value3",
      "prop2": "value4",
    },
    {
      "prop1": "value5",
      "prop2": "value6",
    },
  ];

var arr2 = ['value1','value3', 'newValue'];

// finds all the elements of arr2 that are not in arr1
arr2.filter( 
    val => !arr1.find( arr1Obj => arr1Obj.prop1 === val)
); // outputs "newValue"

4

This is a late answer, but it uses no libraries so some may find it helpful.

/**
 * Returns a non-destructive Array of elements that are not found in
 * any of the parameter arrays.
 *
 * @param {...Array} var_args   Arrays to compare.
 */
Array.prototype.uniqueFrom = function() {
  if (!arguments.length)
    return [];
  var a1 = this.slice(0); // Start with a copy

  for (var n=0; n < arguments.length; n++) {
    var a2 = arguments[n];
    if (!(a2 instanceof Array))
      throw new TypeError( 'argument ['+n+'] must be Array' );

    for(var i=0; i<a2.length; i++) {
      var index = a1.indexOf(a2[i]);
      if (index > -1) {
        a1.splice(index, 1);
      } 
    }
  }
  return a1;
}

Example:

var sheetUsers = ['[email protected]','[email protected]','[email protected]'];
var siteViewers = ['[email protected]','[email protected]','[email protected]'];
var viewersToAdd = sheetUsers.uniqueFrom(siteViewers);  // [[email protected]]
var viewersToRemove = siteViewers.uniqueFrom(sheetUsers);  // [[email protected]]
0
3
 findDiff = (A, B) => {
     return  A.filter(function (a) {
          return !B.includes(a);
     });
 }
1
  • While this code may answer the question, providing additional context regarding why and/or how this code answers the question improves its long-term value. I would recommend you to check SO's official How to Answer article along with the comprehensive blog post from Jon Skeet. Jun 10, 2020 at 11:27
2

Make sorted copies of the arrays first. If the top elements are equal, remove them both. Otherwise remove the element that is less and add it to your result array. If one array is empty, then add the rest of the other array to the result and finish. You can iterate through the sorted arrays instead of removing elements.

// assume x and y are sorted
xi = 0; yi = 0; xc = x.length; yc = y.length;
while ( xi < xc && yi < yc ) {
  if ( x[xi] == y[yi] ) {
    xi += 1;
    yi += 1;
  } else if ( x[xi] < y[yi] ) {
    z.push( x[xi] );
    xi += 1;
  } else {
    z.push( y[yi] );
    yi += 1;
  }
}
// add remainder of x and y to z.  one or both will be empty.
2
  • @Drawnonward: thanks for your suggestion. I understand what you are doing, but I'm wanting to shrink my code to something as simple and lightweight as possible, hopefully leveraging existing jquery code. If I run into a performance problem, I'll consider your idea.
    – Tauren
    Jun 3, 2010 at 7:55
  • Good does not always mean fast, but I took it that way. Enjoy. Jun 3, 2010 at 8:41
1

Maybe jLinq can help you?

It lets you run queries like this against javascript objects.

For example:

var users = [ { name: "jacob", age: 25 },  { name: "bob" , age: 30 }]
var additionalusers = [ { name: "jacob", age: 25 },  { name: "bill" , age: 25 }]

var newusers = jLinq.from(users).except(additionalusers).select();

>>> newusers = [ { name: "bob" , age: 30 } ]

It's a bit overkill for you at the moment, but it's a robust solution that I was glad to learn about.

It can do intersects, unions, handle boolean logic and all kinds of great linq style goodness.

1
  • great looking library, haven't seen that one yet. Still probably a bit much for my immediate needs, but I'll probably give it a whirl for some other things I need to do. Thanks!
    – Tauren
    Jun 3, 2010 at 7:52
0

There is a TC-39 Proposal for Set Methods, currently in Stage 3 (as of Sep 2023)

You can accomplish this with the Set.prototype.difference method:

var x = new Set(["a","b","c","t"]);
var y = new Set(["d","a","t","e","g"]);

var z = y.difference(x) // [ "d", "e", "g" ]

This is currently working behind flags in some browsers, and being developed by others.

Demo

In the meantime, you can polyfill any of the new set methods via npm or checkout MDN's implementation of basic set operations

Further Reading

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.