Check if the values of one array are in another

Question

I need to check if array number 2 contains all of the values in array number 1. I am not aware of any method that does this so I developed one that works, I think. Is there a better way to do this, is this a good solution?

    var contains = function(a1, a2){
var cCount = 0;
for (var i=0; i<a1.length; i++){
     for (var j=0; j<a2.length; j++){
         if (a1[i] == a2[j]){
             cCount++;             
         }}}
if (cCount == a1.length){
    return true;
}

  };

Answer 1

You could check sizes before starting. return false when one is not present instead using a counter. and return true if it reach the end. And use indexof instead looping through a2 every time.

var contains = function(a1, a2){
    if (a1.length>a2.length) return false;
    for (var i=0; i<a1.length; i++){
        if (a2.indexOf(a1[i])<0) return false;
    }
    return true;
}

Answer 2

just a bit simplified code:

function contains(array1, array2){
    var found = false;
    for (i in array1) {
       for (j in array2) {
           if (array1[i] == array2[j]) {
              found = true;
           }
       }
       if (!found) return false;
    }
    return true;
}

another solution I don't really like it but it's shorter...

function contains (arr1, arr2) {
   var specialChar = "|"; // Use any char or a sequence that won't exist in values.
   var str = specialChar + arr2.join(specialChar) + specialChar;
   for (i in arr1) if (str.indexOf(specialChar + arr1[i] + specialChar) == -1) return false;
   return true;
}

Answer 3

Your solution is O(n * n) i.e. order n-squared.

You could sort the arrays first and then sequentially check the elements in the sorted arrays for a match. This will give you an O(n log n) solution. Also you can short circuit the check by ensuring that the size of array2 <= the size of array1.

Evidently this only matters if your arrays are sufficiently big.

Answer 4

You can do this in O(n) if you have a 3rd object that you use to keep track of the items that have been seen already. This assumes that the lookup in seen is O(1) (which presumably it is - What's the big O for JavaScript's array when used as a hash?)

var seen = {};
arr2.forEach(function(el) {
  seen[el] = true;
});

var allContained = true;
arr1.forEach(function(el) {
  if ( allContained && !seen[el] ) {    
    allContained = false;
  }
});

return allContained;

Answer 5

I'd personally use the Array.every() method (though this is, of course, dependent upon a browser that implements this method) in conjunction with Array.indexOf(), which would result in something akin to the following:

var contains = function(needle, haystack){
    return needle.every(function(a){
        return haystack.indexOf(a) > -1;
    });
};

Combining that with the approach you've already produced (testing for browser-support):

var contains = function(needle, haystack){
    if ([].every){
        return needle.every(function(a){
            return haystack.indexOf(a) > -1;
        });
    }
    else {
        var result = true;
        for (var i = 0, len = needle.length; i < len; i++){
            if (haystack.indexOf(needle[i]) === -1) {
                return false;
            }
        }
        return result;
    }
}
var a1 = [1,2,3],
    a2 = [1,2,3,4];
console.log(contains(a1, a2));

JS Fiddle demo.

Note that the else code isn't optimised, it's simply there to demonstrate the code. Having said that, there is a shim for Array.every() at the MDN page (in the references, below) that might make things easier.

References:

• Array.prototype.every().
• Array.prototype.indexOf().