How to compare Between two arrays and check if all items in one are in the second?

Question

I have two arrays with values

a = [1,2,3,4,5];
b = [1,3,5];

if all items from b are in a so i want to return true

another example

a = [123,55,12,66]
b = [123,551]

will return false because 551 is not in a

i tried to go over all items in b and return false if i get an item that isn't in a.

possible duplicate of [Comparing two arrays in Javascript](http://stackoverflow.com/questions/7837456/comparing-two-arrays-in-javascript) — Jai, Jan 01 '14 at 15:44
"i tried to go over all items in b and return false if i get an item that isn't in a." - that is essentially how you would do it. could you post your actual code? — basilikum, Jan 01 '14 at 15:45

cookie monster · Answer 1 · 2014-01-01T15:56:31.797

3

Use .every() with .indexOf().

b.every(function(n) {
    return a.indexOf(n) > -1;
});

You can also create a reusable function, and set the second argument to the array to search.

function itemIsInThis(n) {
    return this.indexOf(n) > -1;
}

And use it like this:

b.every(itemIsInThis, a);

The second argument to .every() (and most other Array iteration methods) will set the this value of the callback, so here we just set this to the a array.

edited Jan 01 '14 at 15:56

answered Jan 01 '14 at 15:51

cookie monster

10,671
4
31
45

I think a closure version `b.every(isIn(a))` would be more concise and performant than the `this` manipulation – Bergi Jan 01 '14 at 16:07
@Bergi: Hmmm... I'm not sure why that would be since you're having to create a new function object. Is there some JS engine optimization disabling that goes on when we set the `this` value? – cookie monster Jan 01 '14 at 16:21
I don't know, but it might be possible. [Actually I can't measure any difference in Opera](http://jsperf.com/array-every-this-vs-closure). Probably `b.every(itemIsInThis, a)` gets optimized to `b.every(itemIsInThis.bind(a))`… – Bergi Jan 01 '14 at 16:33
@Bergi: I doubt that there's a `.bind()` involved. The `.bind()` also creates a function object, and has historically been slower in execution *(though I've not tested recently)*. I'd imagine they pretty much follow the spec, and simply set the `this` value of the call to the callback. There's shouldn't be any overhead since the `this` value is always set in a function call. – cookie monster Jan 01 '14 at 16:42
This algorithm is horribly inefficient (`O(n*m)`, with `O(n+m)` available) and unusable in a situation where the perf would matter anyway, so why waste time polishing crap? – Esailija Jan 01 '14 at 16:44
@Esailija: I like shiny crap? Let's optimize when/where optimization is needed. – cookie monster Jan 01 '14 at 16:46
@Esailija: I must admit though, that my comprehension of big O notation isn't what it should be. My understanding is that `O(n*m)` means that the number of comparisons will be `a.length * b.length`. If that's right, could you please tell me when that would every be true using my solution. I can't conceive of a case where that would happen. – cookie monster Jan 01 '14 at 16:53
I guess if all members of `b` are the same value (or there's just one member), and all happen to match the last value of `a`, then that would be the worse case scenario. – cookie monster Jan 01 '14 at 16:59
@cookiemonster for every item in array A, you search every item in array B. So if both arrays have even as little as 100 000 items you are making 10 000 000 000 operations which is unusable. Whereas with the optimal solution you would only be making 200 000 operations. – Esailija Jan 01 '14 at 17:01
@Esailija: Just to be clear, you're talking about a theoretical worst-case scenario. Since both `.every()` and `.indexOf()` halt early when possible, that'll not normally be the case. Could you provide an answer that would reduce the complexity, and improve computational efficiency? – cookie monster Jan 01 '14 at 17:04
@cookiemonster In common case `.indexOf()` will not find the item which means not halting early - so the practical case will be very close to 10 billion. Anyway there are already answers http://stackoverflow.com/a/20870321/995876 – Esailija Jan 01 '14 at 17:06
@Esailija: Alright, I removed my comment since you updated, though your comment still doesn't quite reflect reality. If it's true that the common case is such that `.indexOf()` will not find a match, and so will not halt early, its failure will cause `.every()` to halt early, and so that'll actually be closer to a best-case scenario. – cookie monster Jan 01 '14 at 17:10
@cookiemonster 5 billion or 10 billion doesn't make a difference, it's the magnitude that matters – Esailija Jan 01 '14 at 17:12
1

@Esailija: Does consistency matter? Should a solution assume that a `.toString()` conversion before comparison will be acceptable? – cookie monster Jan 01 '14 at 17:15

score 2 · Accepted Answer · answered Jan 01 '14 at 15:44

A simple loop is all you need

function allIn(needles, haystack) {
    var i = needles.length;
    while (i--) // loop over all items
        if (haystack.indexOf(needles[i]) === -1) // normal existence check
            return false; // failed test
    return true; // none failed test
}

var a, b;
a = [1,2,3,4,5];
b = [1,3,5];
allIn(b, a); // true

a = [123,55,12,66];
b = [123,551];
allIn(b, a); // false

Johan · Answer 3 · 2014-01-01T15:57:04.473

You can intersect the arrays and compare the result:

Array.prototype.intersect = function (arr1) {

    var r = [], o = {}, l = this.length, i, v;
    for (i = 0; i < l; i++) {
        o[this[i]] = true;
    }
    l = arr1.length;
    for (i = 0; i < l; i++) {
        v = arr1[i];
        if (v in o) {
            r.push(v);
        }
    }
    return r;
};

Array.prototype.containsAll = function (arr) { 
    return arr.intersect(this).length === arr.length;
};

var a = [123,55,12,66],
    b = [123,551],
    c = [1,2,3,4,5],
    d = [1,3,5];

console.log(c.containsAll(d), a.containsAll(b));

http://jsfiddle.net/bgK5q/

adeneo · Answer 4 · 2014-01-01T16:34:22.523

1

You can use $.grep and $.inArray to be more jQuery'ish

$.grep(b, function(el) {return $.inArray(el, a)!=-1});

and to return a boolean compare the length

b.length == $.grep(b, function(el) {return $.inArray(el, a)!=-1}).length;

FIDDLE

edited Jan 01 '14 at 16:34

answered Jan 01 '14 at 16:04

adeneo

312,895
29
395
388

1

Who wants to be jQuerish? Comparing lengths is inefficient and ugly. – Bergi Jan 01 '14 at 16:08
@Bergi - it was just an alternative, `Array.every` and `Array.indexOf` isn't supported in all browsers. – adeneo Jan 01 '14 at 16:15
@adeneo: But neither is `.filter()`. Those are all ECMAScript 5 methods. – cookie monster Jan 01 '14 at 16:23
...maybe you intended to use `$.grep` instead? – cookie monster Jan 01 '14 at 16:26
Your two examples are actually pretty different. The first one will behave more like a `.some()`, while the second will be and `.every()`. – cookie monster Jan 01 '14 at 16:30
`.some()` returns a boolean, `$.grep` just removes the indices that doesn't pass the test, and returns an array, so not really ? – adeneo Jan 01 '14 at 16:33
You've missed my point. OP wants to test that every `b` member is in `a`. Your first example returned a positive (truthy) `.length` if there were *any* matches. Not necessarily all. So yes, really. – cookie monster Jan 01 '14 at 16:38

How to compare Between two arrays and check if all items in one are in the second?

4 Answers4