How to turn this solution from O(n^2) to O(n)?-CodePudding

I am having some problems turning this solution from O(n^2) to O(n). Can anyone kindly help? I am not able to think of any ways to make the time complexity O(n).

//MERGE SORTED ARRAY
/*arr1 = [0,3,4,31]
arr2 = [4,6,30]*/
 
const mergeSortedArrays = (arr1, arr2) => {
  let arr = [];
  let flag = true;
 
  // MERGING ARRAYS
  for (let i = 0; i < arr1.length; i  ) {
    arr.push(arr1[i]);//PUSHING ARRAY1 in arr
  }
  for (let i = 0; i < arr2.length; i  ) {
    arr.push(arr2[i]);//PUSING ARRAY2 in arr
  }
 
  //SORTING ARRAYS
  while (flag) {
    for (let i = 0; i < arr.length; i  ) {
      if (arr[i] > arr[i   1]) {
        let temp = arr[i   1];
        arr[i   1] = arr[i];
        arr[i] = temp;
        flag = true;
      } else {
        flag = false;
      }
    }
  }
 
  console.log(arr1);
  console.log(arr2);
  console.log(arr);//FINAL MERGED & SORTED ARRAY
  // return arr;
  
}
 
mergeSortedArrays([0, 3, 4, 31], [4, 6, 30]);

CodePudding user response：

Try visualising it. It is as if you had two sorted stacks of cards you wanted to sort. You can compare cards at the top of each stack, and put the smaller value on a third stack. And repeat until all cards are on the third sorted stack.

You can keep up two pointers, i and j, one for each array. This will emulate a stack.

The algorithm:

Repeat until the end of both arrays is reached:

   if arr1[i] <= arr2[j]

      push arr1[i] to the merged array and increment i

   else

      push arr2[j] to the merged array and increment j

And some javascript code:

let merged = [];
let i = 0;
let j = 0;
while(i < arr1.length || j < arr2.length){
    if(j == arr2.length || (i < arr1.length && arr1[i] <= arr2[j])){
        merged.push(arr1[i]);
        i  ;
    } else{
        merged.push(arr2[j]);
        j  ;
    }
}

CodePudding user response：

You can use two pointer method, (This solution is based on the assumption that the two lists will always be sorted)

p1=0,p2=0;
arr=[];
while(p1<arr1.length && p2<arr2.length)
{
 if(arr1[p1]<arr2[p2])
   arr.push(arr1[p1  ];
 else
   arr.push(arr2[p2  ];
}

while(p1<arr1.length)
 arr.push(arr1[p1  ]);

while(p2<arr2.length)
 arr.push(arr2[p2  ];

This code will run at the Time Complexity of O(N). I am not familiar with JS so please correct any syntax errors.

CodePudding user response：

You can just Array#concat() and Array#sort() improving also Cyclomatic complexity

Code:

const mergeSortedArrays = (arr1, arr2) => arr1
    .concat(arr2)
    .sort((a, b) => a - b)

const result = mergeSortedArrays([0, 3, 4, 31], [4, 6, 30])

console.log(result)