Merge two sorted arrays in O(n) with extra space
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
#include <iostream>
using namespace std;
int main() {
int arr1[] = {1, 3, 4, 6};
int n = sizeof(arr1)/sizeof(arr1[0]);
int arr2[] = {2, 4, 7, 7};
int m = sizeof(arr2)/sizeof(arr2[0]);
int arr3[n+m];
int i = 0;
int j = 0;
int k = 0;
while(i<n && j<m){
if(arr1[i] < arr2[j]){
arr3[k] = arr1[i];
k++;
i++;
}else if(arr1[i] > arr2[j]){
arr3[k] = arr2[j];
k++;
j++;
}else {
arr3[k] = arr1[i];
k++;
i++;
arr3[k] = arr2[j];
k++;
j++;
}
}
while(i<n){
arr3[k] = arr1[i];
i++;
k++;
}
while(j<m){
arr3[k] = arr2[j];
k++;
j++;
}
for(int i=0; i<n+m ; i++){
cout<<arr3[i]<<" ";
}
}
Cpp
INFO