# Merge Sorted Array LeetCode Solution

Difficulty Level Easy
Shopee Walmart Global techViews 30

## Problem Statement

Merge Sorted Array LeetCode Solution – 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

### 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.

## Approach:

### Solution 01

• We took j=0 to iterate nums2 from the beginning.
• As we know nums1 has a size of m+n & only the first m elements should be in the final array.
• So we replace all the elements from the m index with all the elements of nums2.
• Finally, we’ll sort the array nums1 to get the final sorted array.
• Time complexity: O(nlogn) //as sorting takes nlogn time.

### Solution 02

• Same logic as Solution 01, But here we used resize().
• Resize() will simply keep the elements till m index in muns1 array.
• Then we’ll insert all the elements of the nums2 array by using insert().
• Lastly, we’ll sort the array nums1 to get the final sorted array.
• Time complexity: O(nlogn) //as sorting takes nlogn time.

### Solution 03

• As both solutions 01 & 02 take O(nlogn), now we try to solve it with O(n+m).
• We will use the reverse sorting method.
• We took 3 variables: i (last valid element of nums1 that will present in the final array), j (last element of nums2) & k ( last index of nums1)
• First, while loop will compare nums1 & nums2, and the greater element will be in nums1[k].
• After the loop end if there are still any elements left in an array they will be added by the next 2 while loop.
• Time complexity: O(m+n). ## Code for Merge Sorted Array

### Python Program

```class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i, j, cur = m - 1, n - 1, m + n - 1

while j > -1:
if i > -1 and nums1[i] >= nums2[j]:
nums1[cur] = nums1[i]
i -= 1
else:
nums1[cur] = nums2[j]
j -= 1

cur -= 1```

### Java Program

```class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int last1 = m-1;
int last2 = n-1;

int index = nums1.length-1;

while (last1 >=0 && last2>=0) {
int l = nums1[last1];
int r = nums2[last2];

if (l < r) {
nums1[index--] = r;
last2--;
} else {
nums1[index--] = l;
last1--;
}
}

while (last2 >=0) {
int r = nums2[last2];

nums1[index--] = r;
last2--;
}
}
}```

## Complexity Analysis for Merge Sorted Array LeetCode Solution

Time Complexity: O(m+n) where m and n are the number of non-zero elements in nums1 and nums2 respectively since we are iterating over both arrays in order to merge them

Space Complexity: O(1) since we are doing the merging in place.

Translate »