How to improve performance of nested loops in javascript array manipulation?

Question

I did a coding challenge requiring to merge an input of arrays into a new array by adding only once the duplicated elements and keeping the order of the array elements. My solution is below:

function union(arr){
 let newArr = [];
 let length = arr.length;
 for(let i=0; i< length; i++){
   for(let j=0; j<arr[i].length; j++){
   if(!newArr.includes(arr[i][j])){
     newArr.push(arr[i][j]);
   }
  }
 }
 return newArr;

I wanted to know how can I improve the big O performance of the above solution without using any javascript build in methods as reduce or map etc. Is there a way without using nested loops?

First flat with arrays flat method, then create a Set from the flatted array which will remove duplicates. And you have done in O(n) and two lines of code — quirimmo, Jan 03 '19 at 05:26

score 4 · Accepted Answer · answered Jan 03 '19 at 05:29

4

If you're allowed to, I'd suggest adding all arrays to a Set (duplicate items will be ignored), and then turning the set back into an array:

function union(input){
  const set = new Set(input.flat());
  return [...set];
}

console.log(union([[2, 3], [3, 4]]));

If computational complexity is an issue, it's often a good idea to use sets instead of arrays - Array.prototype.includes is O(N), for example, while Set.prototype.has is O(1).

answered Jan 03 '19 at 05:29

CertainPerformance

356,069
52
309
320

That's exactly what I was going to do :) I thought the question was closed and I just dropped a comment instead of an answer – quirimmo Jan 03 '19 at 05:31

How to improve performance of nested loops in javascript array manipulation?

1 Answers1