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 );

};

Answer 4

Using objects (read: hash tables) in stead of sorting should reduce the amortized complexity to O(m+n):

function bagContains(arr1, arr2) {
    var o = {}
    var result = true;

    // Count all the objects in container
    for(var i=0; i < arr1.length; i++) {
        if(!o[arr1[i]]) {
            o[arr1[i]] = 0;
        }
        o[arr1[i]]++;
    }

    // Subtract all the objects in containee
    // And exit early if possible
    for(var i=0; i < arr2.length; i++) {
        if(!o[arr2[i]]) {
            o[arr2[i]] = 0;
        }
        if(--o[arr2[i]] < 0) {
            result = false;
            break;
        }
    }

    return result;
}

console.log(bagContains([1, 2, 3, 4], [1, 3]));
console.log(bagContains([1, 2, 3, 4], [1, 3, 3]));
console.log(bagContains([1, 2, 3, 4], [1, 3, 7]));

Which yields true, false, false.

Answer 5

Found this on github lodash library. This function use built in functions to solve the problem. .includes() , .indexOf() and .every()

var array1 = ['A', 'B', 'C', 'D', 'E'];
var array2 = ['B', 'C', 'E'];
var array3 = ['B', 'C', 'Z'];
var array4 = [];

function arrayContainsArray (superset, subset) {
  if (0 === subset.length) {
    return false;
  }
  return subset.every(function (value) {
    return (superset.includes(value));
  });
}

 function arrayContainsArray1 (superset, subset) {
   if (0 === subset.length) {
     return false;
   }
   return subset.every(function (value) {
     return (superset.indexOf(value) >= 0);
   });
}

console.log(arrayContainsArray(array1,array2)); //true
console.log(arrayContainsArray(array1,array3)); //false
console.log(arrayContainsArray(array1,array4)); //false

console.log(arrayContainsArray1(array1,array2)); //true
console.log(arrayContainsArray1(array1,array3)); //false
console.log(arrayContainsArray1(array1,array4)); //false

Answer 6

If arr2 is subset of arr1, then Length of set(arr1 + arr2) == Length of set(arr1)

var arr1 = [1, 'a', 2, 'b', 3];
var arr2 = [1, 2, 3];

Array.from(new Set(arr1)).length == Array.from(new Set(arr1.concat(arr2))).length

Answer 7

Here is my solution:

Array.prototype.containsIds = function (arr_ids) {
    var status = true;
    var current_arr = this;
    arr_ids.forEach(function(id) {
        if(!current_arr.includes(parseInt(id))){
            status = false;
            return false; // exit forEach
        }
    });
    return status;
};

// Examples
[1,2,3].containsIds([1]); // true
[1,2,3].containsIds([2,3]); // true
[1,2,3].containsIds([3,4]); // false

Answer 8

As for another approach you may do as follows;

function checkIn(a,b){
  return b.every(function(e){
                   return e === this.splice(this.indexOf(e),1)[0];
                 }, a.slice()); // a.slice() is the "this" in the every method
}

var arr1  = [1, 2, 3, 4],
    arr2  = [1, 2],
    arr3  = [1,2,3,3];
console.log(checkIn(arr1,arr2));
console.log(checkIn(arr1,arr3));

Answer 9

Yet another simple solution is the following:

let a = [1,2,'a',3,'b',4,5]

let b = [1,2,4]

console.log(b.every((i) => a.includes(i)))

Hope it helps

Answer 10

Quick solution here take two arrays if b is longer than it can't be a super set so return false. Then loop through b to see if a contains the element. If so delete it from a and move on if not return false. Worse case scenario is if b is a subset then time will b.length.

function isSuper(a,b){
  var l=b.length,i=0,c;
  if(l>a.length){return false}
  else{
    for(i;i<l;i++){
      c=a.indexOf(b[i]);
      if(c>-1){
        a.splice(c,1);
      }
      else{return false}
    }
    return true;
  }
}

This assumes that inputs will not always be in order and if a is 1,2,3 and b is 3,2,1 it will still return true.