Merge Sorted Array easy

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

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]

Steps

The key idea is to use a three-pointer approach, working from the end of the arrays. We have three pointers:

1. p1: Points to the last element of nums1 (initially m - 1).
2. p2: Points to the last element of nums2 (initially n - 1).
3. p: Points to the last position of the merged array in nums1 (initially m + n - 1).

We compare the elements at p1 and p2. The larger element is placed at position p in nums1. Then, we decrement the corresponding pointer (p1 or p2) and p. We repeat this process until one of the pointers (p1 or p2) reaches the beginning of its respective array. If there are remaining elements in either nums1 or nums2, they are already sorted and in their correct positions.

Explanation

The algorithm works because we're comparing the largest remaining elements in nums1 and nums2 at each step. The larger element is placed at the end of the merged array, ensuring that the resulting array is sorted in descending order (from the end). This avoids the need for extra space or sorting the entire array after merging.

Code

#include <vector>

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

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

        // If there are remaining elements in nums2, copy them to nums1
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p2--;
            p--;
        }
    }
};

Complexity

• Time Complexity: O(m + n) - We iterate through nums1 and nums2 once.
• Space Complexity: O(1) - We use a constant amount of extra space. We modify nums1 in-place.