4.Merge Two Sorted Array

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 a size equal to m + n such that it has enough space 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]

Solution I

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> v;
        int i=0,j=0;
        while(i<m && j<n){
            if(nums1[i] <= nums2[j]){
                v.push_back(nums1[i]);
                i++;
            }
            else{
                v.push_back(nums2[j]);
                j++;
            }
            
        }
        
        while(i<m){
            v.push_back(nums1[i]);
            i++;
        }
        
        while(j<n){
          v.push_back(nums2[j]);
          j++;
        }
        
        
        for(int i=0;i<v.size();i++){
            nums1[i] = v[i];
        }
        
    }
};

This algorithm uses a Time Complexity :O(n) but uses an Extra Space Complexity:O(n)

Solution II

class Solution
{
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
    {
        
        int s = (m + n) - 1;
        m = m - 1;
        n = n - 1;
       
        while (n >= 0)
        {
            if (m>=0 && nums1[m] >= nums2[n])
            {
                nums1[s] = nums1[m];
                m--;
            }
            else
            {
                nums1[s] = nums2[n];
                n--;
            }
            s--;
        }
    }
};

This algorithm uses a Time Complexity :O(n), Space Complexity: O(1)