Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite
2

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?

share|improve this question

4 Answers

up vote 3 down vote accepted 
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/

share|improve this answer
 
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 '10 at 4:22
 
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. –  Matthew Flaschen Jun 3 '10 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 '10 at 4:27
 
works like a champ. thanks! –  Tauren Jun 3 '10 at 7:55
up vote 4 down vote

Here's an alternative using underscore.js:

function inAButNotInB(A, B) {
  return _.filter(A, function (a) {
    return !_.contains(B, a);
  });
}
share|improve this answer
 
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 at 7:46
up vote 1 down vote

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.

share|improve this answer
 
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 '10 at 7:52
up vote 0 down vote

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.
share|improve this answer
 
@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 '10 at 7:55
 
Good does not always mean fast, but I took it that way. Enjoy. –  drawnonward Jun 3 '10 at 8:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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