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

Answer 1

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[1];  
    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(N²) algorithm, so avoid running it on large arrays.

Answer 2

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) {
            this.add(from[i]);
        }
    } 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])) {
                this.add(p, from[p]);
            }
        }
    }
}
IntBag.prototype=[];
IntBag.prototype.size=0;
IntBag.prototype.clone = function() {
    var clone = new IntBag();
    this.each(function(i, count) {
        clone.add(i, count);
    });
    return clone;
};
IntBag.prototype.contains = function(i) {
    if (i in this) {
        return this[i];
    }
    return 0;
};
IntBag.prototype.add = function(i, count) {
    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) {
            union.add(i, count - union.contains(i));
        }
    });
    return union;
};
IntBag.prototype.intersect = function(other) {
    var intersection = new IntBag();
    this.each(function (i, count) {
        if (other.contains(i)) {
            intersection.add(i, Math.min(count, 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.

Answer 3

No one has posted a recursive function yet and those are always fun. Call it like arr1.containsArray( arr2 ).

Demo: http://jsfiddle.net/ThinkingStiff/X9jed/

Array.prototype.containsArray = function ( array /*, index, last*/ ) {

    if( arguments[1] ) {
        var index = arguments[1], last = arguments[2];
    } else {
        var index = 0, last = 0; this.sort(); array.sort();
    };

    return index == array.length
        || ( last = this.indexOf( array[index], last ) ) > -1
        && this.containsArray( array, ++index, ++last );

};