Subscribe to get my new tutorials in your inbox.

Check if an array is a subset of another array in Javascript in O(n) time?

Check if an array is a subset of another array in Javascript?

Hey guys, I hope you are doing well. So today I will share with you a quick snippet of code. How to check if an array is a subset of another array in Javascript? We will discuss the time complexity of our program and try to improvise upon it. So let’s get started.

Let’s define our arrays. I am assuming the arrays are simple and not do have nested objects as elements. For complex array structures, I will come up with another post later. So, for now, let’s focus on simple arrays.

var arr1 = [1,2,3,4,5,6];
var arr2 = [4,3];

So we have two Arrays above. We need to check if arr2 is a subset of arr1. That is whether every element of arr2 is in arr1.

Usual Way

So the first way would be to check using every() method that comes as built-in for JavaScript arrays. Here’s an example.

var check = arr2.every((el) => {
	return arr1.indexOf(el) !== -1;
});
//check will be true in this case

every() – returns true if the callback function (passed to it) returns true for each element in the array, otherwise returns false. And then inside the callback function, I am using indexOf() to find the index of the element. indexOf() is another built-in method provided by JavaScript Arrays, in case you are not aware of it. I have reference links to these two useful methods at the end of this post.

The complexity of the example above is of O(n2) because there are two loops behind the scenes. One loop for every() and the other for indexOf(). So not a very optimal solution for huge arrays.

Why indexOf() is a loop? – Because indexOf is actually looping through the array and checking each element one by one and comparing it with the passed item.

Our main aim would be to bring the complexity down. Let’s try for O(n), which is linear and will perform better.

More optimal way

For that, I will be making use of hashmaps or in simple, JavaScript Objects. First, let’s convert the bigger array into an object,

var arr1 = [1,2,3,4];
var arr2 = [4,3];
var obj = {};
 
//single loop - O(n)
arr1.forEach((el, index) => {
    obj[el] = index;
});
 
/*
this is how obj will look like
obj = {
	"1" : 0,
	"2" : 1,
	"3" : 2,
	"4" : 3
}
*/

Now, let’s loop through the smaller array and check if it is a subset of the bigger array.

//single loop - O(n)
var check = arr2.every((el) => {
  return obj[el] !== undefined; //because 0 is falsy
});
//check will be true in this case

So our 2nd program runs in O(n) complexity, which is optimal.

Give this a try with other Array combinations. Cheers!

References

If you enjoyed this post and want similar articles to be delivered to your inbox directly, you can subscribe to my newsletters. I send out an email every two weeks with new articles, tips & tricks, news, free materials. No spamming, of course.


Write a Comment

Your email address will not be published. Required fields are marked *