Is there a quicker or more efficient way to check that two arrays contain the same values in javascript?
Here is what I'm currently doing to check this. It works, but is lengthy.
var arraysAreDifferent = false;
for (var i = 0; i < array1.length; i++) {
if (!array2.includes(array1[i])) {
arraysAreDifferent = true;
}
}
for (var i = 0; i < array2.length; i++) {
if (!array1.includes(array2[i])) {
arraysAreDifferent = true;
}
}
To reduce computational complexity from O(n ^ 2) to O(n), use Sets instead - Set.has is O(1), but Array.includes is O(n).
Rather than a regular for loop's verbose manual iteration, use .every to check if every item in an array passes a test. Also check that both Set's sizes are the same - if that's done, then if one of the arrays is iterated over, there's no need to iterate over the other (other than for the construction of its Set):
const arr1Set = new Set(array1);
const arr2Set = new Set(array2);
const arraysAreDifferent = (
arr1Set.size === arr2Set.size &&
array1.every(item => arr2Set.has(item))
);
O(n) but each set creation is O(n) itself. Since only one is really needed only arr2Set could be left in, the other removed. With that said, I do like using two sets - it makes the problem more generic and can thus be expanded to cover more things using set algebra.
arr1Set.size === arr2Set.size works, but array1.length === arr2Set.size won't, due to duplicate items of the same value, or due to additional items not contained in the other array (but the other array has duplicate items)
function same(arr1, arr2){
//----if you want to check by length as well
// if(arr1.length != arr2.length){
// return false;
// }
// creating an object with key => arr1 value and value => number of time that value repeat;
let frequencyCounter1 = {};
let frequencyCounter2 = {};
for(let val of arr1){
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
}
for(let val of arr2){
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
}
for(let key in frequencyCounter1){
//check if the key is present in arr2 or not
if(!(key in frequencyCounter2)) return false;
//check the number of times the value repetiton is same or not;
if(frequencyCounter2[key]!==frequencyCounter1[key]) return false;
}
return true;
}
A slight variation on CertainPerformance's answer:
function arraysAreEqual(arr1, arr2) {
// Check if the arrays have the same length
if (arr1.length != arr2.length) {
// Bail out immediately if they are
return false;
}
const arr1Set = new Set(array1);
const arr2Set = new Set(array2);
// Check Size in case one had duplicates, then use has()
return arr1Set.size == arr2Set.size && arr1.every(item => arr2Set.has(item));
}
The array length check is optional if you don't care at all about duplicates, but this still falls short if you wanted to know if the two arrays have exactly the same set of items regardless of their order.
As a side note, .sort() is a mutating function and a bit slow, if you don't want to sort the arrays you are comparing you would need to clone them first into a new array which adds to the overall cost, but:
function arraysAreEqual(array1, array2) {
// Check if the arrays have the same length
if (array1.length !== array2.length) {
// Bail out immediately if they are
return false;
}
// Sort a copy of the arrays or sort the arrays directly if mutation is allowed
const arr1 = [...array1].sort()
const arr2 = [...array2].sort()
// Iterate over the sorted arrays and check values
for (let i = 0; i < arr1.length; i++) {
if (arr1[i] !== arr2[i]) {
// Bail out as there is difference
return false;
}
}
return true;
}
I stumbled onto this question from a rather minor need to optimize how some arrays were being compared and I needed both to worry about the exact set of values and the distinct values in a few cases. Hopefully this is helpful or someone can give feedback to further optimize my answer.
console.log(JSON.stringify(['a','b','c'].sort()) === JSON.stringify(['b','c','a'].sort())); // true[0,1,1]and[0,1]to pass the test.sortis that it's computationally complex -O(n log n), which is worse thanO(n)