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 nums2 into nums1 as one sorted array. The final sorted array should be stored in 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

Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6].

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].

Jump to Solution: Python Java C++ JavaScript C#

Python Solution

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # Start from the end of the arrays
        last = m + n - 1  # Last position in nums1
        m = m - 1         # Last element in nums1
        n = n - 1         # Last element in nums2
        
        # While there are elements to compare
        while m >= 0 and n >= 0:
            if nums1[m] > nums2[n]:
                nums1[last] = nums1[m]
                m -= 1
            else:
                nums1[last] = nums2[n]
                n -= 1
            last -= 1
            
        # If there are remaining elements in nums2
        while n >= 0:
            nums1[last] = nums2[n]
            n -= 1
            last -= 1

Java Solution

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Start from the end of the arrays
        int last = m + n - 1;  // Last position in nums1
        m = m - 1;             // Last element in nums1
        n = n - 1;             // Last element in nums2
        
        // While there are elements to compare
        while (m >= 0 && n >= 0) {
            if (nums1[m] > nums2[n]) {
                nums1[last] = nums1[m];
                m--;
            } else {
                nums1[last] = nums2[n];
                n--;
            }
            last--;
        }
        
        // If there are remaining elements in nums2
        while (n >= 0) {
            nums1[last] = nums2[n];
            n--;
            last--;
        }
    }
}

C++ Solution

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        // Start from the end of the arrays
        int last = m + n - 1;  // Last position in nums1
        m = m - 1;             // Last element in nums1
        n = n - 1;             // Last element in nums2
        
        // While there are elements to compare
        while (m >= 0 && n >= 0) {
            if (nums1[m] > nums2[n]) {
                nums1[last] = nums1[m];
                m--;
            } else {
                nums1[last] = nums2[n];
                n--;
            }
            last--;
        }
        
        // If there are remaining elements in nums2
        while (n >= 0) {
            nums1[last] = nums2[n];
            n--;
            last--;
        }
    }
};

JavaScript Solution

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // Start from the end of the arrays
    let last = m + n - 1;  // Last position in nums1
    m = m - 1;             // Last element in nums1
    n = n - 1;             // Last element in nums2
    
    // While there are elements to compare
    while (m >= 0 && n >= 0) {
        if (nums1[m] > nums2[n]) {
            nums1[last] = nums1[m];
            m--;
        } else {
            nums1[last] = nums2[n];
            n--;
        }
        last--;
    }
    
    // If there are remaining elements in nums2
    while (n >= 0) {
        nums1[last] = nums2[n];
        n--;
        last--;
    }
};

C# Solution

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        // Start from the end of the arrays
        int last = m + n - 1;  // Last position in nums1
        m = m - 1;             // Last element in nums1
        n = n - 1;             // Last element in nums2
        
        // While there are elements to compare
        while (m >= 0 && n >= 0) {
            if (nums1[m] > nums2[n]) {
                nums1[last] = nums1[m];
                m--;
            } else {
                nums1[last] = nums2[n];
                n--;
            }
            last--;
        }
        
        // If there are remaining elements in nums2
        while (n >= 0) {
            nums1[last] = nums2[n];
            n--;
            last--;
        }
    }
}

Complexity Analysis

Time Complexity: O(m + n) where m and n are the lengths of the input arrays
Space Complexity: O(1) as we modify nums1 in-place

Solution Explanation

This solution uses a three-pointer approach working from the end of the arrays:

last: Points to the last position in nums1 where we'll place the next largest element
m: Points to the current element in nums1
n: Points to the current element in nums2

Key points of the solution:

We start from the end because nums1 has extra space at the end
We compare elements from both arrays and place the larger one at the end
This ensures we don't overwrite any elements in nums1 that we still need
After the main loop, we only need to check for remaining elements in nums2
Any remaining elements in nums1 are already in their correct position

The approach is optimal because:

It works in-place without requiring extra space
Each element is only moved once
We don't need to shift elements to make space