Merge Sorted Array

Python Java C++

def merge(nums1, m, nums2, n):
    # Start from the back of both arrays
    i = m - 1
    j = n - 1
    k = len(nums1) - 1
    
    # Fill nums1 from back to front
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1

class Solution {
    // Fill array from back to avoid overwriting
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = nums1.length - 1;

        // Careful, this only works because nums1 is already sorted
        // and we can stop when j < 0 beccause we know the first
        // elements of i will be in place
        while (j >= 0)
            if (i >= 0 && nums1[i] > nums2[j])
                nums1[k--] = nums1[i--];
            else
                nums1[k--] = nums2[j--];
    }
}

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        // Start from the back of both arrays
        int i = m - 1;
        int j = n - 1;
        int k = nums1.size() - 1;
        
        while (j >= 0)
            if (i >= 0 && nums1[i] > nums2[j])
                nums1[k--] = nums1[i--];
            else
                nums1[k--] = nums2[j--];
    }
};

Problem Statement

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 inside nums1 with the first m + n elements sorted in non-decreasing order.

Category: Two Pointers | Difficulty: Easy

Detailed Explanation

Approach

Using a two-pointer approach from the back of both arrays, we fill nums1 from end to start to avoid overwriting elements.

Key Concepts

1. Three Pointers:
   • i: points to last element in nums1
   • j: points to last element in nums2
   • k: points to last position in final array

Algorithm Steps

1. Start from the end of both arrays
2. Compare elements from both arrays
3. Place larger element at the end of nums1
4. Continue until all nums2 elements are placed

Visual Example

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

Step by step:
[4,5,6,0,0,6] i = 2, j = 2
[4,5,6,0,5,6] i = 1, j = 2
[4,5,6,4,5,6] i = 0, j = 2
[4,5,3,4,5,6] i = 0, j = 1
[4,2,3,4,5,6] i = 0, j = 0
[1,2,3,4,5,6] i = 0, j = -1

Time and Space Complexity

• Time Complexity: O(n + m)
• Space Complexity: O(1) - in-place modification

Why Start from the End?

Starting from the end prevents overwriting elements in nums1 that we still need to compare. If we started from the beginning, we'd need extra space to store elements that might be overwritten.

Edge Cases

• When nums2 is empty (n = 0)
• When nums1 is empty (m = 0)
• When all elements from nums1 are greater than nums2
• When all elements from nums2 are greater than nums1