LeetCode 88: Merge Sorted Array Solution in Python Explained

Problem Statement

In LeetCode 88, you’re given two sorted integer arrays nums1 and nums2, and integers m and n representing their respective lengths of valid elements. nums1 has enough space to hold m + n elements (with extra zeros at the end), and your task is to merge nums2 into nums1 in sorted order. This differs from string challenges like LeetCode 87: Scramble String, focusing on array manipulation.

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

Let’s see some cases:

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 nums1, sorted.

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

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

These examples show we’re merging into nums1 in-place.

Understanding the Problem

How do you solve LeetCode 88: Merge Sorted Array in Python? Take nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3. We need [1,2,2,3,5,6] in nums1, using its extra space (0s). A naive copy-and-sort is O((m+n)log(m+n)), but since both arrays are sorted, we can do O(m+n) with pointers. This isn’t a list partitioning like LeetCode 86: Partition List; it’s about merging arrays. We’ll use: 1. Two-Pointer from End: O(m+n) time, O(1) space—our best pick. 2. Two-Pointer with Extra Space: O(m+n) time, O(m+n) space—a baseline.

Let’s dive into the primary solution.

Solution 1: Two-Pointer from End Approach (Primary)

Explanation

Since nums1 has extra space and both arrays are sorted, we merge from the end, placing larger elements at the back of nums1. Use two pointers for nums1 and nums2, and a third for the current position in nums1, moving right to left. This avoids overwriting nums1’s valid elements.

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

• Compare 3 vs. 6, place 6 at end.
• Compare 3 vs. 5, place 5.
• Continue to [1,2,2,3,5,6].

Step-by-Step Example

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

Goal: nums1 = [1,2,2,3,5,6].

• Start: p1 = 2 (3), p2 = 2 (6), p = 5 (end).
• Step 1: 3 < 6.
• nums1[5] = 6, p2 = 1, p = 4.
• nums1 = [1,2,3,0,0,6].
• Step 2: 3 < 5.
• nums1[4] = 5, p2 = 0, p = 3.
• nums1 = [1,2,3,0,5,6].
• Step 3: 3 > 2.
• nums1[3] = 3, p1 = 1, p = 2.
• nums1 = [1,2,3,3,5,6].
• Step 4: 2 == 2.
• nums1[2] = 2, p2 = -1, p = 1.
• nums1 = [1,2,2,3,5,6].
• Step 5: p2 < 0, copy p1: nums1[1] = 2, nums1[0] = 1.
• Finish: nums1 = [1,2,2,3,5,6].

Example 2: nums1 = [1], m = 1, nums2 = [], n = 0

Goal: nums1 = [1].

• Start: p1 = 0, p2 = -1, p = 0.
• Step 1: p2 < 0, copy p1: nums1[0] = 1.
• Finish: nums1 = [1].

Example 3: nums1 = [0], m = 0, nums2 = [1], n = 1

Goal: nums1 = [1].

• Start: p1 = -1, p2 = 0, p = 0.
• Step 1: p1 < 0, copy p2: nums1[0] = 1.
• Finish: nums1 = [1].

How the Code Works (Two-Pointer from End) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    # Line 1: Initialize pointer for nums1 (end of valid elements)
    p1 = m - 1
    # Points to the last valid element in nums1 (e.g., 2 for [1,2,3,0,0,0], m=3)
    # Will move left as we place elements

    # Line 2: Initialize pointer for nums2 (end of array)
    p2 = n - 1
    # Points to the last element in nums2 (e.g., 2 for [2,5,6], n=3)
    # Will move left as we use nums2 elements

    # Line 3: Initialize pointer for current position in nums1
    p = m + n - 1
    # Points to the last position in nums1 (e.g., 5 for length 6)
    # Moves left as we fill nums1 from the end

    # Line 4: Merge while both arrays have elements to compare
    while p1 >= 0 and p2 >= 0:
        # Continues as long as p1 and p2 point to valid indices
        # e.g., p1=2 (3), p2=2 (6) initially

        # Line 5: Compare elements at p1 and p2
        if nums1[p1] > nums2[p2]:
            # If nums1’s element is larger (e.g., 3 > 2 initially false, later true)

            # Line 6: Place nums1[p1] at current position
            nums1[p] = nums1[p1]
            # Copies the larger value to the end (e.g., nums1[3] = 3)
            # Overwrites a 0 or a previously placed value

            # Line 7: Move p1 left
            p1 -= 1
            # Advances p1 to the next element in nums1 (e.g., from 2 to 1)
        else:
            # If nums2’s element is larger or equal (e.g., 3 < 6)

            # Line 8: Place nums2[p2] at current position
            nums1[p] = nums2[p2]
            # Copies the larger value from nums2 (e.g., nums1[5] = 6)

            # Line 9: Move p2 left
            p2 -= 1
            # Advances p2 to the next element in nums2 (e.g., from 2 to 1)

        # Line 10: Move p left
        p -= 1
        # Moves the placement pointer left after each insertion (e.g., from 5 to 4)
        # Prepares for the next comparison

    # Line 11: Copy remaining nums2 elements if any
    while p2 >= 0:
        # If nums2 still has elements (p1 exhausted), copy them
        # e.g., if nums1 is shorter, remaining nums2 goes to the front

        # Line 12: Place remaining nums2[p2]
        nums1[p] = nums2[p2]
        # Copies the element (e.g., nums1[0] = 1 if nums1 was empty)

        # Line 13: Move pointers
        p2 -= 1
        p -= 1
        # Advances both pointers left (e.g., p2 from 0 to -1, p from 0 to -1)

    # No return needed - modifies nums1 in-place

This detailed explanation ensures every step is clear, modifying nums1 efficiently.

Alternative: Two-Pointer with Extra Space Approach

Explanation

Copy nums1’s valid elements to a temporary array, then merge both arrays into nums1 from the start using two pointers. Simpler but uses extra space.

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

• Temp: [1,2,3].
• Merge: Compare and place into nums1.

Step-by-Step Example (Alternative)

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

• Temp: [1,2,3].
• Merge: p1 = 0 (1), p2 = 0 (2), k = 0.
• 1 < 2: nums1[0] = 1, p1 = 1.
• 2 <= 2: nums1[1] = 2, p2 = 1.
• 2 < 5: nums1[2] = 2, p1 = 2.
• 3 < 5: nums1[3] = 3, p1 = 3.
• Copy 5,6: nums1[4] = 5, nums1[5] = 6.
• Finish: [1,2,2,3,5,6].

How the Code Works (Extra Space)

Copy codedef mergeExtraSpace(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    temp = nums1[:m]
    p1, p2, k = 0, 0, 0
    while p1 < m and p2 < n:
        if temp[p1] <= nums2[p2]:
            nums1[k] = temp[p1]
            p1 += 1
        else:
            nums1[k] = nums2[p2]
            p2 += 1
        k += 1
    while p1 < m:
        nums1[k] = temp[p1]
        p1 += 1
        k += 1
    while p2 < n:
        nums1[k] = nums2[p2]
        p2 += 1
        k += 1

Complexity

• Two-Pointer from End:
• Time: O(m+n) – single pass.
• Space: O(1) – in-place.
• Extra Space:
• Time: O(m+n) – single pass.
• Space: O(m) – temp array.

Efficiency Notes

Two-Pointer from End is the LeetCode-preferred solution for its O(1) space, while Extra Space is easier to grasp but less efficient spatially.

Key Insights

• End Merge: Uses extra space cleverly.
• Sorted Input: Enables linear time.
• In-Place: Key constraint advantage.

Additional Example

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

• Goal: [1,2,4,5,6].
• End Merge: Place 6, 5, 4, then 2, 1.

Edge Cases

• Empty nums2: [1,0], m=1, n=0 → [1].
• Empty nums1: [0,0], m=0, [1,2], n=2 → [1,2].
• Single Element: [1,0], m=1, [2], n=1 → [1,2].

Both solutions handle these well.

Final Thoughts

LeetCode 88: Merge Sorted Array in Python is a great intro to array merging. The Two-Pointer from End solution is slick and space-efficient, while Extra Space offers clarity. Want more? Try LeetCode 21: Merge Two Sorted Lists for linked lists or LeetCode 80: Remove Duplicates from Sorted Array II for array tweaks. Ready to practice? Solve LeetCode 88 on LeetCode with [1,2,3,0,0,0] and [2,5,6], aiming for [1,2,2,3,5,6]—test your skills now!