CODEWITHSUNDEEP
javascriptarrayssortingdata-structurestime-complexity
Soumyadeep Chatterjee
Soumyadeep Chatterjee

Reputation: 19

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

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]);

Upvotes: 2

Views: 112

Answers (3)

Yosvel Quintero
Yosvel Quintero

Reputation: 19070

Updated answer based on comments from using Array#sort() to:

const mergeSortedArrays = (arr1, arr2) => {
  const array = { arr1, arr2 }
  const index = { a1: 0, a2: 0 }
  const length = { a1: array.arr1.length, a2: array.arr2.length }
  const merged = []
  let current = 0

  while (current < length.a1 + length.a2) {
    const [a, i] =
      !(index.a1 >= length.a1) &&
      (index.a2 >= length.a2 || array.arr1[index.a1] < array.arr2[index.a2])
        ? ['arr1', 'a1']
        : ['arr2', 'a2']
    merged[current] = array[a][index[i]]
    index[i]++
    current++
  }

  return merged
}

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

console.log(result)

Upvotes: -1

Subash A
Subash A

Reputation: 41

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

let p1 = 0, p2 = 0;
let 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).

Upvotes: 1

Sophia Koulen
Sophia Koulen

Reputation: 312

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++;
    }
}

Upvotes: 2

Related Questions