# 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:I will do a dry run by taking an example :

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;

}

};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=1

ans[]=[1 2 2 3]so now insert the rest of the elemnts of nums2 in the ans[]

soans[] = [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 {I will do a dry run by taking an example :

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--];

}

};nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3i = 2, j = 2 , k = 5

nums1[2] = 3 , nums2[2] = 6 so 3<6

nums1[5] = 6

j = j-1 = 1 and k = 4nums1[]=[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 =0nums1[]=[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 = 1nums1[]=[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= -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 asnums1[]=[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 :

- 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)
- Using the GAP method.

I will attach some useful links below for your reference.

- https://leetcode.com/problems/merge-sorted-array/
- https://www.youtube.com/watch?v=hVl2b3bLzBw&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=6
- https://www.geeksforgeeks.org/efficiently-merging-two-sorted-arrays-with-o1-extra-space/
- 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 ☕