# Check if every element in one array is in a second array

### Question

I have two arrays and I want to check if every element in `arr2` is in `arr1`. If the value of an element is repeated in `arr2`, it needs to be in `arr1` an equal number of times. What's the best way of doing this?

``````arr1 = [1, 2, 3, 4]
arr2 = [1, 2]

checkSuperbag(arr1, arr2)
> true //both 1 and 2 are in arr1

arr1 = [1, 2, 3, 4]
arr2 = [1, 2, 5]

checkSuperbag(arr1, arr2)
> false //5 is not in arr1

arr1 = [1, 2, 3]
arr2 = [1, 2, 3, 3]

checkSuperbag(arr1, arr2)
> false //3 is not in arr1 twice
``````
1
46
12/25/2011 9:41:21 AM

One option is to sort the two arrays, then traverse both, comparing elements. If an element in the sub-bag candidate is not found in the super-bag, the former is not a sub-bag. Sorting is generally O(n*log(n)) and the comparison is O(max(s,t)), where s and t are the array sizes, for a total time complexity of O(m*log(m)), where m=max(s,t).

``````function superbag(sup, sub) {
sup.sort();
sub.sort();
var i, j;
for (i=0,j=0; i<sup.length && j<sub.length;) {
if (sup[i] < sub[j]) {
++i;
} else if (sup[i] == sub[j]) {
++i; ++j;
} else {
// sub[j] not in sup, so sub not subbag
return false;
}
}
// make sure there are no elements left in sub
return j == sub.length;
}
``````

If the elements in the actual code are integers, you can use a special-purpose integer sorting algorithm (such as radix sort) for an overall O(max(s,t)) time complexity, though if the bags are small, the built-in `Array.sort` will likely run faster than a custom integer sort.

A solution with potentially lesser time-complexity is to create a bag type. Integer bags are particularly easy. Flip the existing arrays for the bags: create an object or an array with the integers as keys and a repeat count for values. Using an array won't waste space by creating as arrays are sparse in Javascript. You can use bag operations for sub-bag or super-bag checks. For example, subtract the super from the sub candidate and test if the result non-empty. Alternatively, the `contains` operation should be O(1) (or possibly O(log(n))), so looping over the sub-bag candidate and testing if the super-bag containment exceeds the sub-bag's containment for each sub-bag element should be O(n) or O(n*log(n)).

The following is untested. Implementation of `isInt` left as an exercise.

``````function IntBag(from) {
if (from instanceof IntBag) {
return from.clone();
} else if (from instanceof Array) {
for (var i=0; i < from.length) {
}
} else if (from) {
for (p in from) {
/* don't test from.hasOwnProperty(p); all that matters
is that p and from[p] are ints
*/
if (isInt(p) && isInt(from[p])) {
}
}
}
}
IntBag.prototype=[];
IntBag.prototype.size=0;
IntBag.prototype.clone = function() {
var clone = new IntBag();
this.each(function(i, count) {
});
return clone;
};
IntBag.prototype.contains = function(i) {
if (i in this) {
return this[i];
}
return 0;
};
if (!count) {
count = 1;
}
if (i in this) {
this[i] += count;
} else {
this[i] = count;
}
this.size += count;
};
IntBag.prototype.remove = function(i, count) {
if (! i in this) {
return;
}
if (!count) {
count = 1;
}
this[i] -= count;
if (this[i] > 0) {
// element is still in bag
this.size -= count;
} else {
// remove element entirely
this.size -= count + this[i];
delete this[i];
}
};
IntBag.prototype.each = function(f) {
var i;
foreach (i in this) {
f(i, this[i]);
}
};
IntBag.prototype.find = function(p) {
var result = [];
var i;
foreach (i in this.elements) {
if (p(i, this[i])) {
return i;
}
}
return null;
};
IntBag.prototype.sub = function(other) {
other.each(function(i, count) {
this.remove(i, count);
});
return this;
};
IntBag.prototype.union = function(other) {
var union = this.clone();
other.each(function(i, count) {
if (union.contains(i) < count) {
}
});
return union;
};
IntBag.prototype.intersect = function(other) {
var intersection = new IntBag();
this.each(function (i, count) {
if (other.contains(i)) {
}
});
return intersection;
};
IntBag.prototype.diff = function(other) {
var mine = this.clone();
mine.sub(other);
var others = other.clone();
others.sub(this);
mine.union(others);
return mine;
};
IntBag.prototype.subbag = function(super) {
return this.size <= super.size
&& null !== this.find(
function (i, count) {
return super.contains(i) < this.contains(i);
}));
};
``````

See also "comparing javascript arrays" for an example implementation of a set of objects, should you ever wish to disallow repetition of elements.

23
5/23/2017 12:32:21 PM

Do you have to support crummy browsers? If not, the every function should make this easy.

If arr1 is a superset of arr2, then each member in arr2 must be present in arr1

``````var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; });
``````

Here's a fiddle

EDIT

So you're defining superset such that for each element in arr2, it occurs in arr1 the same number of times? I think filter will help you do that (grab the shim from the preceding MDN link to support older browsers):

``````var isSuperset = arr2.every(function (val) {
var numIn1 = arr1.filter(function(el) { return el === val;  }).length;
var numIn2 = arr2.filter(function(el) { return el === val;  }).length;
return numIn1 === numIn2;
});
``````

Updated Fiddle

END EDIT

If you do want to support older browsers, the MDN link above has a shim you can add, which I reproduce here for your convenience:

``````if (!Array.prototype.every)
{
Array.prototype.every = function(fun /*, thisp */)
{
"use strict";

if (this == null)
throw new TypeError();

var t = Object(this);
var len = t.length >>> 0;
if (typeof fun != "function")
throw new TypeError();

var thisp = arguments;
for (var i = 0; i < len; i++)
{
if (i in t && !fun.call(thisp, t[i], i, t))
return false;
}

return true;
};
}
``````

EDIT

Note that this will be an O(N2) algorithm, so avoid running it on large arrays.