Nerd For Tech
Published in

Nerd For Tech

Merge Sorted Array

(Leetcode)

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
  • -10^9 <= nums1[i], nums2[j] <= 10^9

Approaches :

1. Two Pointer Approach

The basic idea here is to iterate both arrays simultaneously comparing the elements in both.

Time Complexity-O(m+n) where m is the size of array 1 and n is the size of array 2.

Space Complexity-O(m+n), size of vector array.

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

else if(nums1[i]<nums2[j])
{
ans.push_back(nums1[i]);
i++;
}
else
{
ans.push_back(nums1[i]);
ans.push_back(nums2[j]);
i++;
j++;
}
}

while(i<m)
{
ans.push_back(nums1[i]);
i++;
}

while(j<n)
{
ans.push_back(nums2[j]);
j++;
}

nums1=ans;
}
};
I will do a dry run by taking an example :
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
nums1[0] = 1 & sums2[0] = 2 , so 1<2 ,
i = i+1 = 1 and ans[] = [1]
nums1[1] = 2 ,nums2[0] = 2 , 2==2
i = i+1 = 2 and j = j+1 = 1
ans[]=[1 2 2]
nums1[2] = 3 nums2[1] = 5
3<5 , i = i+1 = 3 and j=1
ans[]=[1 2 2 3]
so now insert the rest of the elemnts of nums2 in the ans[]
so ans[] = [1 2 2 3 5 6]
And thus the final answer is obtained.

2. Without using extra space

Time complexity-O(m+n), Space Complexity-O(1)

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

while(j>=0)
nums1[k--] = nums2[j--];
}
};
I will do a dry run by taking an example :
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
i = 2, j = 2 , k = 5
nums1[2] = 3 , nums2[2] = 6 so 3<6
nums1[5] = 6
j = j-1 = 1 and k = 4
nums1[]=[1 2 3 0 0 6]
nums1[2] = 3 nums2[1] = 5 , 3<5
nums1[4] = 5
k = 4-1 = 3 and j = 1-1 =0
nums1[]=[1 2 3 0 5 6]
nums1[2] = 3 nums2[0] = 2
so 3>2
nums[3] = 3 , k = k-1 = 3-1 = 2, i = i-1 = 2-1 = 1
nums1[]=[1 2 3 3 5 6]
nums1[1] =2 nums2[0] = 2
nums[2] = 2 , k = k-1 = 2-1 =1, j=j-1 = 0-1= -1
nums1[]=[1 2 2 3 5 6]
so the program will exit out of the while loop,now since j value is negative so it will not execute the outer loop. Hence we obtain our merged sorted array as nums1[]=[1 2 2 3 5 6]

Hope this clears your concept of solving the above problem using the two approaches. There can be various other approaches such as :

  1. Insertion sort, TC-O(n*m) where n is the size of the first array and m is the size of the second array, SC-O(1)
  2. Using the GAP method.

I will attach some useful links below for your reference.

  1. https://leetcode.com/problems/merge-sorted-array/
  2. https://www.youtube.com/watch?v=hVl2b3bLzBw&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=6
  3. https://www.geeksforgeeks.org/efficiently-merging-two-sorted-arrays-with-o1-extra-space/
  4. https://docs.google.com/document/d/1SM92efk8oDl8nyVw8NHPnbGexTS9W-1gmTEYfEurLWQ/edit

Hope this helps! Keep coding!👩‍🎓💻

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sukanya Bharati

Sukanya Bharati

152 Followers

A happy , motivated & a curious soul if you end up finding me 😎😁.