JavaScript: How to match out-of-order arrays

Question

I'm trying to work out how to match arrays that share the same elements, but not necessarily in the same order.

For example, these two arrays share the same set of elements, even though they're in a different order.

Is there any way to determine whether two arrays contain the same elements?

var search1 = ["barry", "beth", "debbie"];
var search2 = ["beth", "barry", "debbie"];

if (search1 == search2) {
    document.write("We've found a match!");
} else {
    document.write("Nothing matches");
}

I've got a Codepen of this running at the moment over here: http://codepen.io/realph/pen/grblI

Answer 1

The problem with some of the other solutions is that they are of O(n²) complexity, if they're using a for loop inside of a for loop. That's slow! You don't need to sort either—also slow.

We can speed this up to O(2n) complexity¹ by using a simple dictionary. This adds O(2n) storage, but that hardly matters.

JavaScript

var isEqual = function (arr1, arr2) {
    if (arr1.length !== arr2.length) {
        return false;   // no point in wasting time if they are of different lengths
    } else {
        var holder = {}, i = 0, l = arr2.length;
        // holder is our dictionary
        arr1.forEach(function (d) {
            holder[d] = true;    // put each item in arr1 into the dictionary
        })
        for (; i < l; i++) {     // run through the second array
            if (!(arr2[i] in holder)) return false;
            // if it's not in the dictionary, return false
        }
        return true;    // otherwise, return true
    }
}

Test Case

var arr1 = ["barry", "beth", "debbie"],
    arr2 = ["beth", "barry", "debbie"];

console.log(isEqual(arr1,arr2));
// returns true

fiddle

Improvement

As Ahruss pointed out, the above function will return true for two arrays that are seemingly equal. For example, [1,1,2,3] and [1,2,2,3] would return true. To overcome this, simply use a counter in the dictionary. This works because !undefined and !0 both return true.

var isReallyEqual = function (arr1, arr2) {
    if (arr1.length !== arr2.length) {
        return false;   // no point in wasting time if they are of different lengths
    } else {
        var holder = {}, i = 0, l = arr2.length;
        // holder is our dictionary
        arr1.forEach(function (d) {
            holder[d] = (holder[d] || 0) + 1;
            // checks whether holder[d] is in the dictionary: holder[d] || 0
            // this basically forces a cast to 0 if holder[d] === undefined
            // then increments the value
        })
        for (; i < l; i++) {     // run through the second array
            if (!holder[arr2[i]]) {    // if it's not "in" the dictionary
                return false;          // return false
                // this works because holder[arr2[i]] can be either
                // undefined or 0 (or a number > 0)
                // if it's not there at all, this will correctly return false
                // if it's 0 and there should be another one
                // (first array has the element twice, second array has it once)
                // it will also return false
            } else {
                holder[arr2[i]] -= 1;    // otherwise decrement the counter
            }
        }
        return true;
        // all good, so return true
    }
}

Test Case

var arr1 = [1, 1, 2],
    arr2 = [1, 2, 2];

isEqual(arr1, arr2);          // returns true
isReallyEqual(arr1, arr2);    // returns false;

_{1: It's really O(n+m) complexity, whereby n is the size of the first array and m of the second array. However, in theory, m === n, if the arrays are equal, or the difference is nominal as n -> ∞, so it can be said to be of O(2n) complexity. If you're feeling really pedantic, you can say it's of O(n), or linear, complexity.}

Answer 2

Feed your arrays to the following function:

function isArrayEqual(firstArray, secondArray) {
  if (firstArray === secondArray) return true;
  if (firstArray == null || secondArray == null) return false;
  if (firstArray.length != secondArray.length) return false;

  // optional - sort the arrays
  // firstArray.sort();
  // secondArray.sort();

  for (var i = 0; i < firstArray.length; ++i) {
    if (firstArray[i] !== secondArray[i]) return false;
  }
  return true;
}

Now you may be thinking, can't I just say arrayOne.sort() and arrayTwo.sort() then compare if arrayOne == arrayTwo? The answer is no you can't in your case. While their contents may be the same, they're not the same object (comparison by reference).

Answer 3

Sort them firstly. Secondly, if their length is different, then they're not a match. After that, iterate one array and test a[i] with b[i], a being the first array, b the second.

var search1 = ["barry", "beth", "debbie"],
    search2 = ["beth", "barry", "debbie"];

// If length are different, than we have no match.
if ((search1.length != search2.length) || (search1 == null || search2 == null))
  document.write("Nothing matches");

var a = search1.sort(),
    b = search2.sort(),
    areEqual = true;

for (var i = 0; i < a.length; i++) {
  // if any two values from the two arrays are different, than we have no match.
  if (a[i] != b[i]) {
    areEqual = false;
    break; // no need to continue
  }
}

document.write(areEqual ? "We've found a match!" : "Nothing matches");

Answer 4

you can use this function to compare two arrays

function getMatch(a, b) {
    for ( var i = 0; i < a.length; i++ ) {
        for ( var e = 0; e < b.length; e++ ) {
            if ( a[i] === b[e] ){
                return true;
            }
        }
    }   
}

Answer 5

You need to simply sort them, then compare them

function compareArrayItems(array1, array2){
    array1 = array1.sort();
    array2 = array2.sort();

    return array1.equals(array2);
}

fiddle

You can use the equals function provided in How to compare arrays in JavaScript?