Quickest way to check if 2 arrays contain same values in javascript

Question

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

If you need to support old IE and/or are a sociopath you can cast to strings and compare: `console.log(JSON.stringify(['a','b','c'].sort()) === JSON.stringify(['b','c','a'].sort())); // true` — Gavin, Apr 22 '20 at 10:20
@Gavin Thanks for the _sociopath_ comment that made me laugh :) However, from what I understand, OP would want `[0,1,1]` and `[0,1]` to pass the test — blex, Apr 22 '20 at 10:23
An issue with `.sort` is that it's computationally complex - `O(n log n)`, which is worse than `O(n)` — CertainPerformance, Apr 22 '20 at 10:24
@Gavin just a note - that "or" is not exclusive. In fact, either of these could lead to the other. — VLAZ, Apr 22 '20 at 10:33
Highly suggested: [see georg's answer here](https://stackoverflow.com/a/58626840/3689450) which uses set operations. — VLAZ, Apr 22 '20 at 10:36

CertainPerformance · Answer 1 · 2020-04-22T10:37:16.557

4

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

);

edited Apr 22 '20 at 10:37

answered Apr 22 '20 at 10:17

CertainPerformance

356,069
52
309
320

For pure speed, we don't even need two sets. Sure, the overall complexity is still `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. – VLAZ Apr 22 '20 at 10:41
I think both arrays will have to be iterated over at least once regardless, to make sure that each of their elements is contained in the other, and for the computational complexity improvement, one of them needs to be iterated over *again* after that. `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) – CertainPerformance Apr 22 '20 at 10:47

score 0 · Answer 2 · answered Apr 22 '20 at 11:37


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

Quickest way to check if 2 arrays contain same values in javascript

2 Answers2