88. Merge Sorted Array [Leetcode][C++]

#cpp #algorithms #leetcode #programming

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 88. Merge Sorted Array

Brute Force Solution:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { 
    // Brute force approach Time O(NlogN) & Auxiliary Space O(1)
    // Just overwrite nums2 on nums1 starting 
    // from the point where non zero element ends in nums1 
    for(int i=m;i<m+n;i++){
        nums1[i]=nums2[i-m];
    }
    // Sort function has O(NlogN) time complexity
        sort(nums1.begin(),nums1.end()); 
  }
};

Efficient Solution:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { 
    // Optimal Solution Time O(N) & Auxiliary Space O(1)
    // Two pointer approach 
    int p1 = m - 1, p2 = n - 1, curr=m+n-1;
    for (int i = curr; i >= 0 && p2 >=0 ;i--) {  
            if (p1 >= 0 && nums1[p1] > nums2[p2]) 
                nums1[i] = nums1[p1--]; 
            else 
                nums1[i] = nums2[p2--];
        }  
    }
};