'Diff Two Arrays' in Intermediate Algorithm Scripting Challenge

'Diff Two Arrays' in Intermediate Algorithm Scripting Challenge
0

#1

I would like to share my solution to this Challenge, it is not posted among the solutions and I would like to know what you think about it.

function diffArray(arr1, arr2) {
  var newArr = arr1.concat(arr2).sort();
  var a, i =0;
  while (i<newArr.length)
    {
      a = newArr[i];
      if (newArr.indexOf(a) != newArr.lastIndexOf(a))
      {
        newArr.splice(newArr.indexOf(a),newArr.lastIndexOf(a) - newArr.indexOf(a) + 1);
      }
     else
        {
          ++i;
        }
  
    }
  return newArr;
}

diffArray([1, "calf", 3, "piglet"], [1, "calf", 3, 4]);

the Advanced Solution there is very elegant and nice to read, but what about its Complexity? in my Code I put emphasis on Complexity and it’s ‘only’ O(n+m)Log(n+m) (due to sort()), while n,m are lengths of each array.

Tell me please what you think, and what is preferred at workplaces.

Itay.


#2

#3

#4

I have blurred out your solution, campers do not come across it by accident while doing research for themselves.


#5

I could be wrong, but the splice has complexity of O(n) and the indexOf and the lastIndexOf both are O(n). Not sure what the total time complexity would end up being. I will think about it and get back with you or someone else will hopefully respond. Either way, I do not believe your complexity is just O(n+m)Log(n+m).


#6

the sum of O(n) complexities is considered as O(n) complexity in CS. that’s what I’ve been learning at least.
I see it as O(n)Log(n) complexity due to sort() method which slightly bigger. and you always choose the bigger complexity among sub-complexity as code’s main one.


#7

I would agree if they were not nested, but you have them nested within the while loop (which already is O(m+n) ).


#8

I think you’re probably right - lastIndexOf(a) would still check for the whole Array even though it is sorted. I had in mind that It might stop after i < n steps. maybe if I implemented a new lastIndex function for a sorted Array it was different.

Thanks.


#9

When doing my research for this challenging challenge (!) I came up with this. I wish I knew how to think in this way from the outset - so I’m going to include more comments in my code for my own understanding.


function diffArray(arr1, arr2) {
  var newArr = [];
  // Same, same; but different.
  
  var concatArr = arr1.concat(arr2); // Concatinate both arrays
  
 /**
  * Loop through each iteration of concatinate array @concatArr
  * If statement - IF an element in the first array @arr1 
  * OR the second array @arr2 is NOT (remember to prefix with !) included in 
  * @concatArr THEN add that element to the new array @newArr
 */

  for (var i = 0; i < concatArr.length; i++) {    
          if (!arr1.includes(concatArr[i]) || !arr2.includes(concatArr[i])) {
      newArr.push(concatArr[i]);     
    }
  }
  
  return newArr;
}

diffArray([1, 2, 3, 5], [1, 2, 3, 4, 5]);