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 = 3Output: [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 = 0Output: [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 = 1Output: [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 = 3nums1[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=1ans[]=[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 = 3i = 2, j = 2 , k = 5nums1[2] = 3 , nums2[2] = 6 so 3<6nums1[5] = 6j = j-1 = 1 and k = 4nums1[]=[1 2 3 0 0 6]nums1[2] = 3 nums2[1] = 5 , 3<5nums1[4] = 5k = 4-1 = 3 and  j = 1-1 =0nums1[]=[1 2 3 0 5 6]nums1[2] = 3 nums2[0] = 2so 3>2 nums[3] = 3 , k = k-1 = 3-1 = 2, i = i-1 = 2-1 = 1nums1[]=[1 2 3 3 5 6]nums1[1] =2 nums2[0] = 2nums[2] = 2 , k = k-1 = 2-1 =1, j=j-1 = 0-1= -1nums1[]=[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.

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

--

--

## More from Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

## Sukanya Bharati

152 Followers

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