[Interview Question 2] Combine two sorted arrays

Questions:

Given two sorted arrays, arr1 and arr2. arr1 has some empty spaces in the end which equals to the size of arr2. So after combination, all the data can be stored in arr1. Please give an solution with in place operation only.

For example:

arr1 = [1, 3, 5, 7, 0, 0, 0]

arr2 = [2, 4, 6]

return [1, 2, 3, 4, 5, 6, 7]

Notes:

This is a common interview question. Instead of starting from the beginning, we can start from the end. Since arr1 has empty spaces in the end.

In this way, two pointer method can solve this problem with O(m + n) where m and n are the sizes of the elements in arr1 and arr2.

In addition, if we start from the beginning, we may have to move the elements in arr1 towards the end multi-times. The worst time complexity is O(m*n).

See the code below:

void combineSortedArray (vector<int>& arr1, vector<int>& arr2) {
    int m = arr1.size(), n = arr2.size();
    int a = m - n - 1, b = n - 1, c = m-1;
    while(c>=0) {
        if(b<0) break;
        if(a>=0 && b>=0) {
            if(arr1[a] >= arr2[b]) arr1[c--] = arr1[a--];
             else arr1[c--] = arr2[b--];
        }
        else if(a>=0)  arr1[c--] = arr1[a--];
        else if(b>=0)  arr1[c--] = arr2[b--];
        else break;
    }//while
}