0

I want a function, subtract, that will take two arrays, and return all of the elements in array 1 that are not in array 2.

what is the fastest that this can be implemented in js? Is it o(n)?

Zack Burt
  • 8,257
  • 10
  • 53
  • 81

3 Answers3

1

Another option, faster O(n) time, but double memory (still linear), is to create your own hashmap implementation.

Create a hash function. Do a loop through one array and hash all elements. Store (hash, object) pair in another array, call it hash array. Now loop through array 2, and hash each element. Let the hash be the position in hash array, so you can see if you have a collision. If you have a collision check if the object in hash array is the same as the object in current array (that you're looping over).

Adrian
  • 5,603
  • 8
  • 53
  • 85
  • In the js implementation, is it still o(n)? – Zack Burt Mar 15 '12 at 05:18
  • @ZacharyBurt yes; afterall you're doing the implementation so you have control over it. It's 2 for loops: o(n) + o(n) = n(n) runtime. You need an extra o(n) of memory for the hashmap, and that's again 2*o(n)=o(n) – Adrian Mar 15 '12 at 05:24
1

Here's a hash table implementation (using a javascript object as the hash) that is more than 100 times faster (in Chrome) with larger arrays than the brute force lookups using indexOf().

function subtract3(one, two) {
    var hash = {}, result = [], i, len;
    // fill hash with members of second array for easy lookup
    for (i = 0, len = two.length; i < len; i++) {
        hash[two[i]] = true;
    }

    // cycle through first array and find ones that are not in two
    for (i = 0, len = one.length; i < len; i++) {
        if (!(one[i] in hash)) {
            result.push(one[i]);
        }
    }
    return(result);
}

Here's a jsperf test comparing this option with a couple other options: http://jsperf.com/array-subtraction

jfriend00
  • 683,504
  • 96
  • 985
  • 979
  • @Raynos - yes that is correct. I was assuming this was an array of strings or numbers. The OP did not specify. – jfriend00 Mar 15 '12 at 14:52
0

You cannot generically solve this for O(n) unless you want to restrict your arrays to objects that can be serialized to strings

function substract(one, two) {
    var result = []
    for (var i = 0, len = one.length; i < len; i++) {
        var value = one[i]
        if (two.indexOf(value) === -1) {
            result.push(value)
        }
    }
    return result
}

Or if you want to use array iterators

function substract(one, two) {
    return one.filter(function (value) {
        return two.indexOf(value) === -1
    })
}
Raynos
  • 166,823
  • 56
  • 351
  • 396