Problem Description

You have two sorted integer arrays nums1 and nums2 that are already arranged in non-decreasing order. You also have two integers m and n that tell you how many valid elements are in nums1 and nums2 respectively.

Your task is to merge nums2 into nums1 so that nums1 becomes one sorted array containing all elements from both arrays.

Here are the key requirements:

1. nums1 has a total length of m + n to accommodate all elements
2. The first m positions in nums1 contain the valid elements to be merged
3. The last n positions in nums1 are filled with zeros and serve as placeholder space
4. nums2 has length n and contains n valid elements
5. The merge must be done in-place - you need to modify nums1 directly rather than creating a new array
6. The final result should have all elements sorted in non-decreasing order

For example, if nums1 = [1,2,3,0,0,0] with m = 3 and nums2 = [2,5,6] with n = 3, after merging, nums1 should become [1,2,2,3,5,6].

The solution uses a two-pointer approach that starts from the end of both arrays. By comparing elements from the back and placing the larger element at the end of nums1, we can efficiently merge the arrays without needing extra space. The process continues until all elements from nums2 have been placed into nums1.

Intuition

The key insight comes from recognizing that we have extra space at the end of nums1 that we can utilize. If we tried to merge from the beginning, we'd run into a problem: placing elements from nums2 at the front of nums1 would overwrite the original elements we haven't processed yet.

Think about it this way - if we start from the front and want to insert nums2[0] into its correct position in nums1, we might need to shift existing elements in nums1 to make room. This shifting would be complicated and inefficient.

However, if we work backwards from the end, we have a brilliant advantage: the end of nums1 is empty (filled with zeros)! We can safely place elements there without worrying about overwriting any unprocessed data.

By comparing the largest unprocessed elements from both arrays (which are at positions m-1 and n-1 initially), we can determine which element should go at the very end of the merged array. The larger of the two should occupy position m+n-1. Then we move our pointers accordingly and repeat.

This backwards approach naturally handles the merging without requiring any extra space or complex shifting operations. Each element is placed exactly once in its final position. Even if all elements from nums2 are larger than those in nums1, or vice versa, the algorithm handles these edge cases gracefully.

The beauty of this solution is that it transforms what could be a complex insertion problem into a simple comparison and placement problem, taking advantage of the pre-allocated space in nums1.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution implements a two-pointer technique that processes both arrays from right to left. Here's how the algorithm works:

We initialize three pointers:

• i = m - 1: Points to the last valid element in nums1
• j = n - 1: Points to the last element in nums2
• k = m + n - 1: Points to the last position in the merged array (end of nums1)

The main loop continues as long as there are elements from nums2 to process (j >= 0). In each iteration:

1. Compare elements: We check if there's still an element in nums1 to compare (i >= 0) and if that element is greater than the current element in nums2 (nums1[i] > nums2[j])

2. Place the larger element:

   • If nums1[i] is larger, we place it at position k and decrement i
   • Otherwise (including when i < 0), we place nums2[j] at position k and decrement j

3. Move the destination pointer: After placing an element, we decrement k to move to the next position

The algorithm naturally handles edge cases:

• When all elements from nums1 have been processed (i < 0), we simply copy the remaining elements from nums2
• When all elements from nums2 have been placed, the loop ends, and any remaining elements in nums1 are already in their correct positions

This approach achieves O(m + n) time complexity with only a single pass through both arrays, and O(1) space complexity since we're modifying nums1 in-place without using any additional data structures.

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works step by step.

Initial Setup:

• nums1 = [4, 5, 6, 0, 0, 0], m = 3
• nums2 = [1, 2, 3], n = 3
• We need to merge these into nums1 = [1, 2, 3, 4, 5, 6]

Initialize pointers:

• i = 2 (pointing to nums1[2] = 6)
• j = 2 (pointing to nums2[2] = 3)
• k = 5 (pointing to the last position in nums1)

Step 1:

• Compare nums1[2] = 6 with nums2[2] = 3
• Since 6 > 3, place 6 at position k = 5
• nums1 = [4, 5, 6, 0, 0, 6]
• Update: i = 1, k = 4

Step 2:

• Compare nums1[1] = 5 with nums2[2] = 3
• Since 5 > 3, place 5 at position k = 4
• nums1 = [4, 5, 6, 0, 5, 6]
• Update: i = 0, k = 3

Step 3:

• Compare nums1[0] = 4 with nums2[2] = 3
• Since 4 > 3, place 4 at position k = 3
• nums1 = [4, 5, 6, 4, 5, 6]
• Update: i = -1, k = 2

Step 4:

• Now i < 0, so we only consider nums2[2] = 3
• Place 3 at position k = 2
• nums1 = [4, 5, 3, 4, 5, 6]
• Update: j = 1, k = 1

Step 5:

• Still i < 0, place nums2[1] = 2 at position k = 1
• nums1 = [4, 2, 3, 4, 5, 6]
• Update: j = 0, k = 0

Step 6:

• Still i < 0, place nums2[0] = 1 at position k = 0
• nums1 = [1, 2, 3, 4, 5, 6]
• Update: j = -1, k = -1

Result: The loop ends since j < 0. All elements have been successfully merged in sorted order: nums1 = [1, 2, 3, 4, 5, 6]

This example demonstrates how working backwards prevents us from overwriting unprocessed elements and efficiently places each element exactly once in its final position.

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m is the number of initialized elements in nums1 and n is the number of elements in nums2. The algorithm iterates through all elements from nums2 (controlled by the condition j >= 0), and for each element, it performs a constant-time comparison and assignment operation. In the worst case, it also processes all m elements from nums1. Therefore, the total number of operations is proportional to m + n.

The space complexity is O(1). The algorithm modifies nums1 in-place without using any additional data structures. It only uses a fixed number of variables (k, i, and j) regardless of the input size, resulting in constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Starting from the Beginning Instead of the End

A common mistake is attempting to merge from the beginning of the arrays. This approach seems intuitive but causes problems:

Incorrect Approach:

def merge_wrong(nums1, m, nums2, n):
    i, j, k = 0, 0, 0
    while i < m and j < n:
        if nums1[i] <= nums2[j]:
            # This overwrites valid elements!
            nums1[k] = nums1[i]
            i += 1
        else:
            nums1[k] = nums2[j]
            j += 1
        k += 1

Why it fails: When merging from the front, you risk overwriting elements in nums1 that haven't been processed yet. Since we need to preserve all valid elements, this leads to data loss.

Solution: Always merge from the end to avoid overwriting unprocessed elements. The empty space at the end of nums1 provides a safe zone to place elements without losing data.

Pitfall 2: Incorrect Loop Termination Condition

Another frequent error is using the wrong condition for the main loop:

Incorrect Implementation:

def merge_wrong(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    # Wrong: stops when either array is exhausted
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    # Need additional code to handle remaining elements

Why it fails: This stops as soon as one array is exhausted, requiring additional logic to handle remaining elements. If nums1 is exhausted first, you need to copy remaining elements from nums2. If nums2 is exhausted first, the remaining nums1 elements are already in place.

Solution: Use while j >= 0 as the loop condition. This ensures all elements from nums2 are processed. If nums1 elements remain after nums2 is exhausted, they're already in their correct positions.

Pitfall 3: Off-by-One Errors with Indices

Index management is crucial, and off-by-one errors are easy to make:

Common Mistakes:

# Wrong: Using length instead of last index
i = m  # Should be m - 1
j = n  # Should be n - 1

# Wrong: Incorrect array bounds
k = m + n  # Should be m + n - 1

# Wrong: Forgetting to decrement after placement
nums1[k] = nums2[j]
# Missing: j -= 1 or k -= 1

Solution: Remember that array indices are 0-based. The last valid element in nums1 is at index m - 1, not m. Similarly, the last position in the merged array is m + n - 1. Always decrement the appropriate pointer after using it.

Pitfall 4: Not Handling Empty Arrays

Failing to consider edge cases where one array might be empty:

Problematic Assumption:

def merge_unsafe(nums1, m, nums2, n):
    # Assumes both arrays have elements
    if nums1[m-1] <= nums2[0]:
        # Just append nums2 to nums1
        for i in range(n):
            nums1[m + i] = nums2[i]
        return

Why it fails: This crashes when m = 0 (accessing nums1[-1]) or n = 0 (accessing nums2[0]).

Solution: The main algorithm naturally handles these cases. When m = 0, the condition i >= 0 is immediately false, so all elements come from nums2. When n = 0, the loop while j >= 0 never executes, leaving nums1 unchanged.