# LeetCode 88: Merge Sorted Array

> How I solved the Merge Sorted Array problem with linear runtime and constant auxiliary space complexity.

Published: 2026-08-12

[View the HTML version](https://itsmeyaw.id/blog/leetcode-88/)

## Challenge Description

You can view the challenge [here](https://leetcode.com/problems/merge-sorted-array?envType=study-plan-v2&envId=top-interview-150).

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.

## Intuition

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)$$:

```cpp []
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // Initialize the collector here.
        vector<int> temp(m + n, 0);
        int counter1 = 0;
        int counter2 = 0;
        for (int index = 0; index < m + n; index++) {
            // First, check that both counters are valid, then compare the values.
            if (counter2 < n && counter1 < m &&
                    nums1[counter1] > nums2[counter2]) {
                temp[index] = nums2[counter2];
                counter2++;
            }
            // In this case, either nums2[counter2] >= nums1[counter1],
            // or one of the arrays is exhausted.

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

            // This is when nums2 has more elements.
            // We could check counter2 < n here, but it is implied by
            // the preceding cases.
            else {
                temp[index] = nums2[counter2];
                counter2++;
            }
        }
        // Set nums1 to the actual answer.
        nums1 = temp;
    }
};

```

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:

```cpp []
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int counterNums2 = 0;
        for (int index = 0; index < m + n && counterNums2 < n; index++) {

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

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

                if (index >= m) {
                    counterNums2++;
                }
            }
        }
    }
};
```

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.

## Approach

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`.

### Proof

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.

## Complexity

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

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

## Code

```cpp []
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // Start from the last indices.
        int counter1 = m - 1;
        int counter2 = n - 1;
        // Start from the end of the array.
        for (int index = m + n - 1; index >= 0; index--) {
            // Use the same logic as before, but fill the array with
            // the largest values first.
            if (counter1 >= 0 && counter2 >= 0 &&
                    nums1[counter1] < nums2[counter2]) {
                nums1[index] = nums2[counter2];
                counter2--;
            } else if (counter1 >= 0) {
                nums1[index] = nums1[counter1];
                counter1--;
            } else {
                nums1[index] = nums2[counter2];
                counter2--;
            }
        }
    }
};
```