88. Merge Sorted Array

📝 Problem Details

• Title: 88. Merge Sorted Array
• Link: https://leetcode.com/problems/merge-sorted-array/
• Difficulty: Easy
• Tags/Categories: Sorting Two-Pointers

input: nums1 & nums2 ⇒ they are both sorted in ascending order m & n representing the number of elements in nums1 and nums2 merge nums1 and nums2into a single array in ascending order store the result inside nums1

💡 Solution 1 : Concatenate and Sort

Copy elements from nums2 into the remaining positions in nums1 Sort nums1 in-place and return it

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // copy elements from nums2 to nums1
        for(int i=0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
 
        // sort the merged array
        sort(nums1.begin(), nums1.end());
    }
};

Time Complexity: O(x log x) where x is the sum of n+m Space Complexity: O(1)

---

💡 Solution 2 : Three Pointers (Merging from the end)

Use three pointers:

• p1 = m-1 ⇒ Last element of valid (non-zero) `nums1
• p2 = n-1 ⇒ Last element of nums2
• p = m + n - 1 ⇒ Last position of `nums1

Compare elements from nums1[p1] and nums2[p2], placing the larger of the two into nums1[p] If any elements remain in nums2, copy them

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m-1; // last non-zero position in nums1
        int p2 = n-1; // last position in nums2
        int p = m + n - 1; // last position in nums1 including empty values
 
        // merge from the back
        while(p1 >= 0 && p2 >= 0) {
 
            // choose the larger value between p1 and p2 and put it at the back of nums1
            if(nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p--;
                p1--;
            }
            else {
                nums1[p] = nums2[p2];
                p--;
                p2--;
            }
        }
 
        // copy remaining elements from nums2
        while(p2 >= 0) {
            nums1[p] = nums2[p2];
            p--;
            p2--;
        }
    }
};

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