Merge Sorted Array

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, merge nums2 into nums1 as one sorted array. The number of elements initialized in nums1 and nums2 are m and n respectively. Assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Examples

Example 1:

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

Output: [1,2,2,3,5,6]

Example 2:

Input:
nums1 = [1], m = 1
nums2 = [], n = 0

Output: [1]

Approach 1: Brute Force

Explanation

  1. Copy all elements from nums2 to the end of nums1.
  2. Sort the entire nums1 array.

Time Complexity: O((m+n) log(m+n))

Space Complexity: O(1) (assuming in-place sorting)

Implementation

Java Solution

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Copy nums2 elements to the end of nums1
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }

        // Sort nums1
        Arrays.sort(nums1);
    }
}

C++ Solution

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // Copy nums2 elements to the end of nums1
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }

        // Sort nums1
        sort(nums1.begin(), nums1.end());
    }
};

Approach 2: Optimal (Three Pointers)

Explanation

  1. Start from the end of both arrays.
  2. Compare elements and place the larger one at the end of nums1.
  3. Move backwards in the arrays until all elements are placed.

Time Complexity: O(m+n)

Space Complexity: O(1)

Implementation

Java Solution

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1; // Pointer for nums1
        int p2 = n - 1; // Pointer for nums2
        int p = m + n - 1; // Pointer for merged array

        while (p2 >= 0) {
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
    }
}

C++ Solution

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1; // Pointer for nums1
        int p2 = n - 1; // Pointer for nums2
        int p = m + n - 1; // Pointer for merged array

        while (p2 >= 0) {
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
    }
};

Explanation with Example

Let's walk through the optimal approach using Example 1:

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

  1. Initialize pointers:

    • p1 = 2 (last element of nums1)
    • p2 = 2 (last element of nums2)
    • p = 5 (last position of merged array)

  2. Compare nums1[p1] and nums2[p2]:

    • 3 > 6? No, place 6 at nums1[p]
    • nums1 = [1,2,3,0,0,6], p2--, p--

  3. Compare nums1[p1] and nums2[p2]:

    • 3 > 5? No, place 5 at nums1[p]
    • nums1 = [1,2,3,0,5,6], p2--, p--

  4. Compare nums1[p1] and nums2[p2]:

    • 3 > 2? Yes, place 3 at nums1[p]
    • nums1 = [1,2,3,3,5,6], p1--, p--

  5. Compare nums1[p1] and nums2[p2]:

    • 2 > 2? No, place 2 from nums2 at nums1[p]
    • nums1 = [1,2,2,3,5,6], p2--, p--

  6. p2 is now -1, so we're done.

The final merged and sorted array is [1,2,2,3,5,6].

This approach is optimal because it only requires one pass through the arrays, resulting in a time complexity of O(m+n) and space complexity of O(1) as it modifies the array in-place.