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]);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++;
}
}
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).
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)