Check if every element in one array is in a second array
Problem
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
Solution
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
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 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)
See also "comparing javascript arrays" for an example implementation of a set of objects, should you ever wish to disallow repetition of elements.
Discussion
View additional discussion.