Merge Sorted Array — Editorial

Opening the reading…

Intuitionwhy the empty suffix makes a backward merge possible

The first m positions of nums1 and all n positions of nums2 are sorted sequences; the zeros after position m - 1 are only empty storage. A normal merge chooses the smallest front value, but writing that value from the front would overwrite an element in nums1 that has not been compared yet.

The empty slots are at the end, so reverse the direction. Compare the largest valid value in each array and write the larger one into the last available slot. That write cannot destroy unread data: every unread value lies to its left. Once nums1's valid portion is exhausted, any remaining nums2 values can be copied into the beginning; if nums2 is exhausted first, nums1's remaining values are already in their final positions.

Approach

Set i to m - 1, j to n - 1, and k to m + n - 1, because i and j must start at the ends of the actual sorted data while k starts at the final slot available for the merged result.

While both i and j are valid, compare nums1[i] and nums2[j], because the larger of these two values is exactly the next value that belongs at the rightmost unfilled position.

Write the larger value into nums1[k] and move k left, because each iteration fills one final position and must not leave the write pointer behind.

Move i when nums1[i] is larger; otherwise move j, including ties, because the chosen value has been consumed and the other value remains available for a later position.

Continue until one valid portion is empty, because no comparison is possible after that point and all positions to the right are already finalized.

Copy nums2[j] through nums2[0] into the remaining slots while j is valid, because those values have not been written yet; if nums1 runs out, its remaining values already occupy the correct prefix.

Complexitylinear work and constant working memory

MEASURE	BOUND	WHY
Time	O(m + n)	Each valid value from nums1 and nums2 is examined at most once, and each value that must move is written once. The two pointers only move left, so no element is revisited by the merge.
Space	O(1) extra	Only i, j, k, and a temporary comparison value use working memory. The modified nums1 array is required output and is excluded from the extra-space bound; the bound stays O(1) for every input shape, including when either valid portion is empty.

Here m is the number of valid values initially in nums1, and n is the number of values in nums2.

Annotated solutionC++ · in-place reverse merge · complete judge submission

CPPCompare the two valid suffixes and fill nums1 from its last slot toward the front.

#include <vector>

using namespace std;

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};