# Solution For Merge Sorted Array

The Merge Sorted Array problem on LeetCode asks for a solution to merge two sorted integer arrays into one sorted array. The two input arrays are already sorted in non-descending order, and one of the arrays has enough space at the end to hold all the elements of the two arrays.

Here’s a detailed solution to the problem:

“`
void merge(vector& nums1, int m, vector& nums2, int n) {
int i = m – 1;
int j = n – 1;
int k = m + n – 1;

``````while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
``````

}
“`

Explanation:

We start by initializing three pointers i, j, and k. i and j point to the last elements of nums1 and nums2, respectively. k points to the last position of the merged array, which is m + n – 1.

We then iterate through the arrays in reverse order using a while loop. We compare the values at i and j and use the greater one to fill the kth position in nums1. We decrement k, i, or j based on which value we chose. We continue this process until either we reach the beginning of nums2 (j < 0) or we have filled all positions in nums1 (k < 0).

This algorithm has a time complexity of O(m+n) and a space complexity of O(1), since we are only modifying the existing arrays, and not creating any new data structures.

## Step by Step Implementation For Merge Sorted Array

```class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// two get pointers for nums1 and nums2
int p1 = 0;
int p2 = 0;
// set pointer for nums1
int p = 0;

// compare elements from nums1 and nums2
// and add the smallest one into nums1
while ((p1 < m) && (p2 < n))
nums1[p++] = (nums1[p1] < nums2[p2]) ? nums1[p1++] : nums2[p2++];

// if there are still elements to add
if (p1 < m)
System.arraycopy(nums1, p1, nums1, p, m + n - p1);
if (p2 < n)
System.arraycopy(nums2, p2, nums1, p, m + n - p2);
}
}```
```def merge(nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""

# two get pointers for nums1 and nums2
p1 = m - 1
p2 = n - 1

# set pointer for nums1
p = m + n - 1

# while there are still elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1

# add missing elements from nums2
nums1[:p2 + 1] = nums2[:p2 + 1]```
```function mergeSortedArray(arr1, arr2) {
// check input
if (!arr1 || !arr2) {
return null;
}

let mergedArray = [];

let i = 0;
let j = 0;

// compare elements from each array and push the smaller element into the merged array
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) {
mergedArray.push(arr1[i]);
i++;
} else {
mergedArray.push(arr2[j]);
j++;
}
}

// if there are elements left in arr1, push them all into the merged array
while (i < arr1.length) {
mergedArray.push(arr1[i]);
i++;
}

// if there are elements left in arr2, push them all into the merged array
while (j < arr2.length) {
mergedArray.push(arr2[j]);
j++;
}

return mergedArray;
}```
```vector mergeSortedArray(vector& nums1, vector& nums2) {
// create an empty vector to store the merged array
vector mergedArray;

// create two pointer variables to keep track of the current index
// of each array
int pointer1 = 0;
int pointer2 = 0;

// while both pointers are within the bounds of their respective arrays
while (pointer1 < nums1.size() && pointer2 < nums2.size()) {
// compare the values at the current indices of each array
// and push the smaller value into the merged array
if (nums1[pointer1] <= nums2[pointer2]) {
mergedArray.push_back(nums1[pointer1]);
pointer1++;
}
else {
mergedArray.push_back(nums2[pointer2]);
pointer2++;
}
}

// if there are any remaining elements in array 1, append them to the merged array
while (pointer1 < nums1.size()) {
mergedArray.push_back(nums1[pointer1]);
pointer1++;
}

// if there are any remaining elements in array 2, append them to the merged array
while (pointer2 < nums2.size()) {
mergedArray.push_back(nums2[pointer2]);
pointer2++;
}

return mergedArray;
}```
```public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {
// two get pointers for nums1 and nums2
int p1 = 0;
int p2 = 0;
// set pointer for nums1
int p = 0;

// compare elements from nums1 and nums2
// and add the smallest one into nums1
while ((p1 < m) && (p2 < n))
nums1[p++] = (nums1[p1] < nums2[p2]) ? nums1[p1++] : nums2[p2++];

// if there are still elements to add
if (p1 < m)
while (p1 < m)
nums1[p++] = nums1[p1++];

if (p2 < n)
while (p2 < n)
nums1[p++] = nums2[p2++];
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]