Merge Sorted Array

📝 Problem Summary

You are given two sorted arrays, nums1 and nums2, and two integers m and n representing the number of valid elements in each.
The goal is to merge them into a single sorted array stored in nums1.

nums1 has length m + n, with the last n spaces set to 0 to hold the merged result.

💡 Solution 1 — Traditional Merge Using an Extra Array

This mirrors the merge step of merge sort. Although not the optimal in-place solution, it's conceptually simple for beginners. Note that this will not pass the leetcode test cases because it doesn't store the result in nums1

🔧 Python Code

# traditional merge-sort style solution using an additional array

def merge(nums1, m, nums2, n):
    # additional array to store sorted elements
    sorted = []
    i, j = 0, 0

    # merge while both arrays still have elements
    while i < m and j < n:
        if nums1[i] < nums2[j]:
            sorted.append(nums1[i])
            i += 1
        else:
            sorted.append(nums2[j])
            j += 1

    # transfer remaining elements
    if i == m:
        while j < n:
            sorted.append(nums2[j])
            j += 1
    else:
        while i < m:
            sorted.append(nums1[i])
            i += 1

    print(sorted)

# Example run:
merge([1,2,3,0,0,0], 3, [2,5,6], 3)

💡 Optimal Approach — Reverse Merge (No Extra Space)

Because nums1 has empty space at the end, the optimal approach is to fill it from the back:

Key ideas:

i = m - 1 → last initialized element of nums1
j = n - 1 → last element of nums2
k = m + n - 1 → last index of the final merged array
Compare from the end and place the larger value at nums1[k]
Copy remaining nums2 elements (if any)

This avoids overwriting needed values and uses O(1) additional memory.

🔧 Python Code

# Since the solution should be stored in nums1, merge in reverse order

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """

        # edge cases
        if m == 0:
            for i in range(n):
                nums1[i] = nums2[i]
            return

        if n == 0:
            print(nums1)
            return

        # start at the end of each array
        i = m - 1
        j = n - 1

        # pointer for the insertion position in nums1
        k = (n + m) - 1

        # merge backwards
        while i != -1 and j != -1:
            if nums1[i] >= nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

        # if nums2 still has elements, place them in nums1
        while j != -1:
            nums1[k] = nums2[j]
            k -= 1
            j -= 1

        print(nums1)


# Write your own test cases here:
s = Solution()
s.merge([1,2,3,0,0,0], 3, [2,5,6], 3)
s.merge([2,5,6,0,0,0], 3, [1,2,3], 3)