Problem
First array has n positive numbers, and they are sorted in the non-descending order.
Second array has 2n numbers: first n are also positive and sorted in the same way but the last n are all zeroes.
Merge the first array into the second and return the latter. You should get 2n positive integers sorted in the non-descending order.
Example
{
"first": [1, 3, 5],
"second": [2, 4, 6, 0, 0, 0]
}
Output:
[1, 2, 3, 4, 5, 6]
Solution
function merge_one_into_another(first, second) {
// Write your code here.
var n = first.length;
var top = n-1;
var bottom = n-1;
var k = second.length -1;
while(top >= 0 && bottom >=0){
if(first[top] >= second[bottom]) {
second[k] = first[top];
top-=1;
k-=1;
} else {
second[k] = second[bottom];
bottom-=1;
k-=1;
}
}
while(top >=0){
second[k] = first[top];
top-=1;
k-=1;
}
return second;
}
Time and Space Complexity
Time Complexity : O(1)
Space Complexity: O(n)
Tech Corner 