jQuery Disjoint

Question

Hello,

I have two arrays:

var a = new Array(1,2,3,4);
var b = new Array(5,3,2,6);

I want to find out which elements are in array a but not in array b and which elements are in b but not in a?

I know one way is to iterate through them each, but is there a more efficient way?

Thank you for your time.

Answer 1

you can sort them first (a.sort()), and then it's a simple iteration.

Answer 2

You could try the following:

var aNotInB = $.grep(a, function($e) { return $.inArray($e, b) == -1; });
var bNotInA = $.grep(b, function($e) { return $.inArray($e, a) == -1; });

You could define this as a jquery function:

$.disjoin = function(a, b) {
    return $.grep(a, function($e) { return $.inArray($e, b) == -1; });
};

var aNotInB = $.disjoin(a,b);
var bNotInA = $.disjoin(b,a);

Answer 3

You have to look at each element of both array to get the difference of them. So there is no other way than iterating both array:

Array.prototype.diff = function(otherArray) {
    var diff = [], found;
    for (var i=0; i<this.length; i++) {
        found = false;
        for (var j=0; j<otherArray.length; j++) {
            if (this[i] == otherArray[j]) {
                found = true;
                break;
            }
        }
        if (!found) {
            diff.push(this[i]);
        }
    }
    return diff;
};

var a = [1,2,3,4],
    b = [5,3,2,6];
var aDiffB = a.diff(b),
    bDiffA = b.diff(a);

You can skip some comparisons when the arrays are sorted and start with the inner loop with the element after the last match and break it if the value is larger:

Array.prototype.diff = function(otherArray) {
    var diff = [], found, startAt = 0,
        a = this.sort(),
        b = otherArray.sort();
    for (var i=0; i<a.length; i++) {
        found = false;
        for (var j=startAt; j<b.length; j++) {
            if (a[i] > b[j]) {
                break;
            }
            if (a[i] == b[j]) {
                found = true;
                startAt = j + 1;
                break;
            }
        }
        if (!found) {
            diff.push(a[i]);
        }
    }
    return diff;
};

But sorting both array does also cost.

Answer 4

PHP's in_array() function was ported to Javascript some time back. I've used it from time to time. Additionally, the array_diff() function was also ported over.

function in_array(needle, haystack, argStrict) {
    // http://kevin.vanzonneveld.net 
    var key = '', strict = !!argStrict;

    if (strict) {
        for (key in haystack) {
            if (haystack[key] === needle) {
                return true;
            }
        }
    } else {
        for (key in haystack) {
            if (haystack[key] == needle) {
                return true;
            }
        }
    }

    return false;
}

function array_diff() {
    // *     example 1: array_diff(['Kevin', 'van', 'Zonneveld'], ['van', 'Zonneveld']);
    // *     returns 1: ['Kevin']
    var arr1 = arguments[0], retArr = {};
    var k1 = '', i = 1, k = '', arr = {};

    arr1keys:
    for (k1 in arr1) {
        for (i = 1; i < arguments.length; i++) {
            arr = arguments[i];
            for (k in arr) {
                if (arr[k] === arr1[k1]) {
                    // If it reaches here, it was found in at least one array, so try next value
                    continue arr1keys; 
                }
            }
            retArr[k1] = arr1[k1];
        }
    }

    return retArr;
}