What is the best way to find all items are deleted / inserted from original array - Javascript?

Question

I have originalArray list number (when app not change). After do something, i have modifiedArray which some items were inserted/ deleted from originalArray. I wrote function to find all items are deleted/ inserted from originalArray.

var modifiedArray = [1,3,5,6,7,8,9,10,11];
var originalArray = [1,2,3,4,5,6];
var insertedArray = [];
var deletedArray = [];
function work(){
        for(var i = 0 ; i< originalArray.length ; i++){
            if(modifiedArray.indexOf(originalArray[i]) == -1){
                deletedArray.push(originalArray[i]);
        }
    }

    for(var i = 0 ; i< modifiedArray.length ; i++){
            if(originalArray.indexOf(modifiedArray[i]) == -1){
                insertedArray.push(modifiedArray[i]);
        }
    }
}

Is that the best way to find all items are deleted / inserted from original array ?

If anyone has other suggestion, feel free to tell us.

Thanks you so much.

"the best" was from what perspective? It works - so currently it is the best 1 of 1. — zerkms, Jun 21 '16 at 07:52
@Juhana except that OP is also looking at newly added elements. — Quentin Roy, Jun 21 '16 at 08:06
@Roque Yes, that is what "set difference" means. All they have to do is run whatever method they choose twice with the parameters reversed (like they're doing now in their own code so I assumed that part was clear). — JJJ, Jun 21 '16 at 08:08
what about `var modifiedArray = [1], originalArray = [1,1,1];` ? — le_m, Jun 21 '16 at 08:12
@Juhana As it is a quite expensive operation, a solution that can do both in a single shot is better. — Quentin Roy, Jun 21 '16 at 08:16
can insertions only happen at the end? are the array elements unique? you must specify your problem more thoroughly — le_m, Jun 21 '16 at 08:22
@NinaScholz I guess you can sort both array before the comparison. — Ömer Erden, Jun 21 '16 at 08:30
i do not need sorted data, but if the data *is already sorted*, then only one loop is necessary. — Nina Scholz, Jun 21 '16 at 08:32
@NinaScholz Actually i was trying to solve this issue with that idea, its possible and nearly done. but its not perfect O(n) . — Ömer Erden, Jun 21 '16 at 08:38

score 0 · Answer 1 · answered Jun 21 '16 at 08:10

0

You could use a hash table and use it as remainder for the deleted items.

var modifiedArray = [1, 3, 5, 6, 7, 8, 9, 10, 11],
    originalArray = [1, 2, 3, 4, 5, 6],
    insertedArray = [],
    deletedArray = [],
    hash = Object.create(null);

originalArray.forEach(function (a) {
    hash[a] = {value:a};
});

insertedArray = modifiedArray.filter(function (a) {
    var r = !hash[a];
    if (hash[a]) {
        delete hash[a];
    }
    return r;
});

deletedArray = Object.keys(hash).map(function (k) { return hash[k].value; });

console.log(insertedArray);
console.log(deletedArray);

answered Jun 21 '16 at 08:10

Nina Scholz

376,160
25
347
392

Not my downvote, but this is a lot more complex than the original code, and it won't work reliably with any other data types than numbers and strings or mixed content arrays (e.g. it thinks `["1", {foo: 2}]` and `[1, {bar: 3}]` are identical.) – JJJ Jun 21 '16 at 08:17
1

sorry, i write answers to given problems, not for thing, which could be, like you state. should an answer consider more than the op has stated? – Nina Scholz Jun 21 '16 at 08:21
+1 for what you just said (about given problems), but I personally think it's overcomplicated and might have been rewritten better (in both of readability and optimisations (hidden classes and redundant allocations)) – zerkms Jun 21 '16 at 08:23
If an answer has a major gothca, like it works specifically only for the data types that are in the question, it's best to at least mention it in the answer. For two reasons: the code in the question is often a simplification of the actual code (although in this case the OP does say that it's an array of numbers) and more importantly, Stack Oveflow's idea is to create a knowledge database for everyone. People who come here later with the same problem don't necessarily have an array of numbers so they need to know that the solution is not universal. – JJJ Jun 21 '16 at 08:27

OzW · Answer 2 · 2016-06-21T08:15:33.883

0

SORRY, THIS IS A VERY COSTLY SOLUTION (THANKS zerkms FOR THE COMMENT)

Your algorithm runs through both arrays. I think you can achieve what you want by only going through the original array:

For each item in the original array:

If it is IN the modified array > remove it from both arrays
If it is NOT IN the modified array > do nothing

When you're done, the modified array will contain only items which were not in the original array (inserted) and the original array will contain only items which were not in the modified array (deleted).

edited Jun 21 '16 at 08:15

answered Jun 21 '16 at 08:11

OzW

848
1
11
24

Your solution is even worse than `O(n^2)` from the OP, since you do additional linear array mutations. – zerkms Jun 21 '16 at 08:12
@zerkms isn't array removal in O(n) and thereby this solution in O(n²)? – le_m Jun 21 '16 at 08:16
@le_m algorithmically it is still `O(n^2)` but now you mutate arrays (which is not free) – zerkms Jun 21 '16 at 08:18

score 0 · Answer 3 · answered Jun 21 '16 at 08:27

var modifiedArray = [1,3,5,6,7,8,9,10,11];
var originalArray = [1,2,3,4,5,6];

function difference(a,b){
 return a.filter(function(x) { return b.indexOf(x) < 0 })
}

var insertedArray = difference(modifiedArray, originalArray);
var deletedArray = difference(originalArray, modifiedArray);

alert("Inserted: " + JSON.stringify(insertedArray));
alert("Deleted: " + JSON.stringify(deletedArray));

You can also use lodash library. It has many functions to operate with arrays/objects.

var modifiedArray = [1,3,5,6,7,8,9,10,11];
var originalArray = [1,2,3,4,5,6];
var insertedArray = _.difference(modifiedArray, originalArray);
var deletedArray = _.difference(originalArray, modifiedArray);

What is the best way to find all items are deleted / inserted from original array - Javascript?

3 Answers3