LeetCode 88: Merge Sorted Array - All Solutions Explained

Problem Statement

The Merge Sorted Array problem, LeetCode 88, is an easy-difficulty challenge where you’re given two sorted integer arrays nums1 and nums2, and their respective lengths m and n. You must merge nums2 into nums1 in sorted order, utilizing the fact that nums1 has enough space (length m + n) to hold all elements. The operation must be performed in-place.

Constraints

• nums1.length == m + n
• nums2.length == n
• 0 ≤ m, n ≤ 200
• 1 ≤ m + n ≤ 200
• -10^9 ≤ nums1[i], nums2[j] ≤ 10^9

Example

Copy codeInput: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: Merge [1,2,3] and [2,5,6] into [1,2,2,3,5,6] in nums1.

Copy codeInput: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: nums2 is empty, so nums1 remains [1].

Copy codeInput: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: nums1 is empty, so copy [1] into nums1.

Understanding the Problem

We need to merge two sorted arrays into nums1 in-place, maintaining sorted order. Key points:

• nums1 has extra space at the end (zeros) to accommodate nums2.
• We can’t use extra space beyond O(1) for the optimal solution.
• We’ll explore two solutions:
  • Two Pointers from End : Optimal in-place method (best solution).
  • Copy and Sort : Simple but uses extra space/time.

Solution 1: Two Pointers from End (Best Solution)

Intuition

Since nums1 has enough space and both arrays are sorted, start from the end of both arrays and fill nums1 from right to left, comparing the largest elements.

How It Works

1. Use three pointers:
   • p1 at the end of nums1’s valid elements (m-1).
   • p2 at the end of nums2 (n-1).
   • p at the end of nums1’s total space (m+n-1).
2. While p2 >= 0 and p1 >= 0:
   • If nums1[p1] > nums2[p2], place nums1[p1] at p, decrement p1 and p.
   • Else, place nums2[p2] at p, decrement p2 and p.
3. If p2 remains, copy leftover nums2 elements to nums1.

Step-by-Step Example

For nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3:

• p1 = 2, p2 = 2, p = 5.
• 3 vs 6: nums1[5] = 6, p2 = 1, p = 4.
• 3 vs 5: nums1[4] = 5, p2 = 0, p = 3.
• 3 vs 2: nums1[3] = 3, p1 = 1, p = 2.
• 2 vs 2: nums1[2] = 2, p1 = 0, p = 1.
• 1 vs 2: nums1[1] = 2, p2 = -1, p = 0.
• Copy 1: nums1[0] = 1.
• Result: [1,2,2,3,5,6].

004aad Python Code (Best Solution)

Copy codedef merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1 = m - 1  # Pointer for nums1
    p2 = n - 1  # Pointer for nums2
    p = m + n - 1  # Pointer for merged array
    
    # While both arrays have elements
    while p2 >= 0 and p1 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    
    # If nums2 has remaining elements
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

# Test cases
nums1 = [1,2,3,0,0,0]
merge(nums1, 3, [2,5,6], 3)
print(nums1)  # Output: [1,2,2,3,5,6]

nums1 = [1]
merge(nums1, 1, [], 0)
print(nums1)  # Output: [1]

nums1 = [0]
merge(nums1, 0, [1], 1)
print(nums1)  # Output: [1]

Detailed Walkthrough

• Pointers : p1 and p2 track the largest unmerged elements; p fills nums1.
• Comparison : Place the larger value at the end, moving backwards.
• Cleanup : Handle any remaining nums2 elements.

Complexity

• Time Complexity : O(m + n), single pass through both arrays.
• Space Complexity : O(1), in-place operation.

Why It’s the Best

• No extra space required.
• Linear time with optimal use of sorted property.004aad
• Interview-preferred for its efficiency and elegance.

Solution 2: Copy and Sort

Intuition

Copy nums2 into the empty space of nums1, then sort the entire array.

How It Works

1. Copy nums2 elements into nums1 starting at index m.
2. Sort nums1 using a built-in sorting function.

Python Code

Copy codedef merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    # Copy nums2 into nums1
    for i in range(n):
        nums1[m + i] = nums2[i]
    
    # Sort the entire array
    nums1.sort()

# Test cases
nums1 = [1,2,3,0,0,0]
merge(nums1, 3, [2,5,6], 3)
print(nums1)  # Output: [1,2,2,3,5,6]

nums1 = [1]
merge(nums1, 1, [], 0)
print(nums1)  # Output: [1]

nums1 = [0]
merge(nums1, 0, [1], 1)
print(nums1)  # Output: [1]

Detailed Walkthrough

• Copy : Fill nums1’s extra space with nums2.
• Sort : Use Python’s Timsort to order the array.

Complexity

• Time Complexity : O((m + n) log(m + n)), due to sorting.
• Space Complexity : O(1), assuming in-place sort (Python’s sort is O(log n) internally).

Pros and Cons

• Pros : Simple and leverages built-in functions.
• Cons : Slower and doesn’t utilize the sorted property of inputs.

Comparison of Solutions

Table

Edge Cases to Consider

• Empty nums2: m > 0, n = 0 → nums1 unchanged.
• Empty nums1: m = 0, n > 0 → Copy nums2 into nums1.
• Single element: [1] and [] or [0] and [1].
• All elements equal: [2,2] and [2].

Final Thoughts

• Two Pointers from End : The best solution—fast, in-place, and leverages the problem’s sorted nature.
• Copy and Sort : Easy but inefficient. Master the two-pointer approach for its practicality in array merging problems. Try merging k sorted arrays as a follow-up!