LeetCode 88: Merge Sorted Array

You can view the challenge here.

You are given two integer arrays, nums1 and nums2, sorted in non-decreasing order. The integers m and n represent the number of meaningful elements in nums1 and nums2, respectively.

Merge the arrays into a single sorted array and store the result in nums1. The function should not return the result.

nums1 has a length of m + n, where its first m elements contain the values to merge, while its final n elements are placeholders set to 0 and should be ignored. nums2 has a length of n.

For example:

• nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], and n = 3 produces [1,2,2,3,5,6].
• nums1 = [1], m = 1, nums2 = [], and n = 0 produces [1].
• nums1 = [0], m = 0, nums2 = [1], and n = 1 produces [1]. The 0 is only a placeholder because nums1 must have enough space for the result.

The constraints are 0 <= m, n <= 200, 1 <= m + n <= 200, and every array value is between -10^9 and 10^9. The follow-up is to solve the problem in O(m+n) time.

This challenge is easy to solve, but achieving a runtime of $\mathcal{O}(m+n)$ and an auxiliary space complexity of $\mathcal{O}(1)$ is a bit more challenging.

I wanted to learn C++, so I tried to solve this problem in C++ with a runtime of $\mathcal{O}(m+n)$:

  
1
class Solution {
2
public:
3
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
        // Initialize the collector here.
5
        vector<int> temp(m + n, 0);
6
        int counter1 = 0;
7
        int counter2 = 0;
8
        for (int index = 0; index < m + n; index++) {
9
            // First, check that both counters are valid, then compare the values.
10
            if (counter2 < n && counter1 < m &&
11
                    nums1[counter1] > nums2[counter2]) {
12
                temp[index] = nums2[counter2];
13
                counter2++;
14
            }
15
            // In this case, either nums2[counter2] >= nums1[counter1],
16
            // or one of the arrays is exhausted.
17

18
            // This is the case when nums1 is not yet exhausted and
19
            // nums2[counter2] >= nums1[counter1].
20
            else if (counter1 < m) {
21
                temp[index] = nums1[counter1];
22
                counter1++;
23
            }
24

25
            // This is when nums2 has more elements.
26
            // We could check counter2 < n here, but it is implied by
27
            // the preceding cases.
28
            else {
29
                temp[index] = nums2[counter2];
30
                counter2++;
31
            }
32
        }
33
        // Set nums1 to the actual answer.
34
        nums1 = temp;
35
    }
36
};

However, this results in $\mathcal{O}(m + n)$ auxiliary space, and I feel that we can do better. The fact that nums1 already has $m + n$ elements seems like a clue that an optimization is possible.

To achieve $\mathcal{O}(1)$ auxiliary space, I cannot create an additional array to store the temporary solution. This means that I need to swap values in nums1. I tried a similar approach: I iterate over the indices and swap the smallest values between nums1 and nums2 at the current indices. This resulted in the following incorrect code:

  
1
class Solution {
2
public:
3
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
        int counterNums2 = 0;
5
        for (int index = 0; index < m + n && counterNums2 < n; index++) {
6

7
            // Check whether the current value in nums2 is larger than
8
            // the next one. If so, swap them.
9
            if (counterNums2 + 1 < n && nums2[counterNums2] > nums2[counterNums2 + 1]) {
10
                int temp = nums2[counterNums2 + 1];
11
                nums2[counterNums2 + 1] = nums2[counterNums2];
12
                nums2[counterNums2] = temp;
13
            }
14

15
            // Swap in place if nums1 is larger than nums2, or fill the
16
            // rest of nums1 with the remaining values from nums2.
17
            if (nums1[index] > nums2[counterNums2] || index >= m) {
18
                int temp = nums2[counterNums2];
19
                nums2[counterNums2] = nums1[index];
20
                nums1[index] = temp;
21

22
                if (index >= m) {
23
                    counterNums2++;
24
                }
25
            }
26
        }
27
    }
28
};

This code does not work because I lose the sorted-array invariant for nums2. To fix it, I could sort nums2 after every swap, but that would result in a time complexity of $\mathcal{O}((m+n)(n \log n))$.

So the question is whether there is a way to write the result in place without breaking the invariant that both nums1 and nums2 are sorted. Then I realized that the extra space in nums1 could act as auxiliary space for storing the partial answer. I can use this space first to save space.

The unintuitive part of the approach is solving the problem in reverse order. I use the same intuition as before, but write the result in place. Because $m + n \geq m$ (the size of nums1 is greater than or equal to the number of its actual elements), I can safely iterate from the largest indices downward and store the temporary result without worrying that it will overwrite an actual value in nums1.

Let $c_1$, $c_2$, and $i$ denote the indices of the largest unmerged elements in nums1 and nums2, and the next output position, respectively. I initialize them as follows:

• $c_1 = m - 1$
• $c_2 = n - 1$
• $i = m + n - 1$

Each iteration decreases $i$ by one, and exactly one of $c_1$ or $c_2$ also decreases by one. This means that $i = c_1 + c_2 + 1$ at all times.

I was worried that I might overwrite nums1[c1] during an iteration, so I checked whether that could happen.

As long as nums2 has an unmerged element ($c_2 \geq 0$), $i \geq c_1 + 1 > c_1$. Therefore, writing an element to nums1[i] cannot overwrite the unread element at nums1[c_1].

If nums2 is exhausted, then $c_2 = -1$ and $i = c_1$, which means that the remaining elements of nums1 are already in their final positions.

• Time complexity: $\mathcal{O}(m+n)$

• Space complexity: $\mathcal{O}(1)$

  
1
class Solution {
2
public:
3
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
        // Start from the last indices.
5
        int counter1 = m - 1;
6
        int counter2 = n - 1;
7
        // Start from the end of the array.
8
        for (int index = m + n - 1; index >= 0; index--) {
9
            // Use the same logic as before, but fill the array with
10
            // the largest values first.
11
            if (counter1 >= 0 && counter2 >= 0 &&
12
                    nums1[counter1] < nums2[counter2]) {
13
                nums1[index] = nums2[counter2];
14
                counter2--;
15
            } else if (counter1 >= 0) {
16
                nums1[index] = nums1[counter1];
17
                counter1--;
18
            } else {
19
                nums1[index] = nums2[counter2];
20
                counter2--;
21
            }
22
        }
23
    }
24
};