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--];
}
}
};
All suggestions are welcome. Please upvote if you like it. Thank you.
Top comments (0)