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 nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

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]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

Follow-up: Can you come up with an algorithm that runs in O(m + n) time?

My Approach :

Brute Force Method:

1. Copy all the elements of nums2 to nums1 from nums1 location m to m+n.
2. Then use the sort function in nums1.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=m; i<m+n; i++){
            nums1[i] = nums2[i-m];
        }

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

The Loop has a time complexity of O(n) because it iterates through each element once.

The time complexity of the merge function is O((m+n) log(m+n)), where m is the size of nums1 and n is the size of nums2.

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

Follow-Up Answer:

In this approach, I utilize two variables, i and j, to track the elements of nums1 and nums2 respectively. I create a new vector, nums3, to store the merged values.

I employ a while loop to iterate until either i reaches the end of nums1 or j reaches the end of nums2. Within this loop, I compare the elements pointed out by i and j, pushing the smaller one into nums3.

Once the while loop terminates, I check which vector still has elements remaining and append them to nums3.

Finally, I copy the sorted elements from nums3 back to nums1 to complete the merging process.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int>nums3;

        int i=0, j=0;
        while(i<m && j<n){
            if(nums1[i] <= nums2[j]){
                nums3.push_back(nums1[i]);
                i++;
            }
            else{
                nums3.push_back(nums2[j]);
                j++;
            }
        }

        for(int k=i; k<m; k++){
            nums3.push_back(nums1[k]);
        }

        for(int k=j; k<n; k++){
            nums3.push_back(nums2[k]);
        }     

        for(int k=0; k<nums1.size(); k++){
            nums1[k] = nums3[k];
        }
    }
};

• The while loop contributes O(m + n).
• The subsequent two for loops contribute O(m) and O(n) respectively.
• The last loop contributes O(m + n).

Time Complexity : O(m + n), where m is the size of nums1 and n is the size of nums2.

Optimal Approach :

In this Optimal Approach, we prioritize reducing space complexity by avoiding the use of an additional vector, unlike in the First Approach.

We begin by initializing both pointers from the end of their respective arrays. This strategic placement allows us to efficiently compare elements and directly place the larger element at the end of nums1. The algorithm iterates through both arrays, continuously updating the elements in nums1 until all elements from nums2 have been merged.

By employing this technique, we optimize space usage and maintain a clear and concise merging process.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1, j=n-1;

        // pointer for the merged array starting from end of nums1
        int k = m+n-1;

        while(i>=0 && j>=0){
            if(nums1[i] > nums2[j]){
                nums1[k] = nums1[i];
                k--;
                i--;
            }
            else{
                nums1[k] = nums2[j];
                k--;
                j--;
            }
        }

        while(j>=0){
            nums1[k] = nums2[j];
            k--;
            j--;
        }    
    }
};

Time Complexity : O(m + n), where m is the size of nums1 and n is the size of nums2.