Merge Sorted Array

Problem Description

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

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Examples

Constraints

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10⁹ <= nums1[i], nums2[j] <= 10⁹

Merging Backward to Avoid Overwrites

If we merge nums1 and nums2 from the beginning, we must shift elements in nums1 to the right to make space for elements from nums2. This increases the time complexity to O(n * (m + n)). To solve this in-place in linear time, we can merge starting from the back. Since the last n slots of nums1 are empty, we place pointers at the end of the active elements of nums1 (m - 1), the end of nums2 (n - 1), and the final index of nums1 (m + n - 1). We compare the values at nums1 and nums2 from right to left, place the larger element at the write index, and move the pointers backward. This avoids overwriting any elements in nums1 before they are read.

Solution 1: Backward Two Pointers Merge

Fill nums1 starting from its last slot to execute an in-place merge.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; // last element of nums1
        int j = n - 1; // last element of nums2
        int k = m + n - 1; // write pointer in nums1

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

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        i = m - 1       # last element of nums1
        j = n - 1       # last element of nums2
        k = m + n - 1   # write pointer in nums1
        
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

#include <vector>

class Solution {
public:
    void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n) {
        int i = m - 1; // last element of nums1
        int j = n - 1; // last element of nums2
        int k = m + n - 1; // write pointer in nums1

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

Complexity Analysis

• Time Complexity: O(m + n) since we iterate through the target elements from right to left.
• Space Complexity: O(1) auxiliary space as the merge operation is done in-place inside nums1.

Where It Breaks

This solution relies on nums1 having n pre-allocated empty spaces at the end. If nums1 is not large enough to hold all elements, we must allocate a new array of size m + n, which increases space complexity to O(m + n).

Common Mistakes

• Forgetting remaining elements of nums2: Stopping the merge loop early when i < 0. If elements remain in nums2, they must be copied over to nums1. The loop while (j >= 0) ensures we continue until all elements of nums2 are placed.
• Off-by-one errors on initial pointers: Starting pointers at m or n instead of m - 1 and n - 1.

Frequently Asked Questions

Why don’t we need to copy remaining elements of nums1? If nums2 is exhausted first (j < 0), the remaining elements of nums1 are already in their correct sorted positions at the beginning of nums1, so no additional copy is needed.

Can we sort the array after appending? Appending nums2 to nums1 and running sort() takes O((m+n) log(m+n)) time, which is less optimal than the O(m+n) two-pointer approach.

← All Problems