Merging sorted arrays is a fundamental problem in computer science. The task is to combine two sorted arrays into one sorted array, maintaining the order. The **Merge Sorted Array** presents this classic problem with a twist — you are asked to merge the arrays **in-place**. This means that instead of using extra space, you must merge the second array into the first array directly.

In this article, we will explore two methods to solve this problem: a **brute force approach** and an **efficient Two-Pointer approach**. We’ll also go through the Java code for both solutions and explain each step in simple language.

## Problem Description:

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}

Problem Link :Merge Sorted Array – LeetCode

## Solutions:

### Approach 1: Brute Force Solution

The brute force approach is the simplest method to solve the problem, but it is not the most efficient. In this method, we can create a new array to hold the elements from both `nums1`

and `nums2`

. Once the elements are copied, we sort the new array and copy the sorted values back into `nums1`

.

### Steps:

**Create a new array**to store the merged result.**Copy all elements**from`nums1`

and`nums2`

into this new array.**Sort**the new array.**Copy the sorted elements**back into`nums1`

.

#### Java Code:

```
import java.util.Arrays;
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// Create a new array to store merged elements
int[] merged = new int[m + n];
// Copy elements from nums1
for (int i = 0; i < m; i++) {
merged[i] = nums1[i];
}
// Copy elements from nums2
for (int j = 0; j < n; j++) {
merged[m + j] = nums2[j];
}
// Sort the merged array
Arrays.sort(merged);
// Copy back the sorted array to nums1
for (int i = 0; i < merged.length; i++) {
nums1[i] = merged[i];
}
}
}
```

#### Explanation:

- We first create a new array
`merged`

of size`m + n`

to hold all the elements of both arrays. - We copy the valid elements of
`nums1`

(i.e., the first`m`

elements) into`merged`

. - Then, we copy the
`n`

elements of`nums2`

into the`merged`

array. - We use
`Arrays.sort()`

to sort the merged array. - Finally, we copy the sorted elements back into
`nums1`

.

### Time and Space Complexity:

**Time Complexity:**O((m + n) log (m + n)) — Sorting dominates the time complexity.**Space Complexity:**O(m + n) — We are using extra space to store the merged array.

Although this method works, it’s not efficient due to the extra space required and the sorting step, which increases time complexity.

## Approach 2: Efficient Two-Pointer Solution

The brute force method works, but it is not space-efficient. We can solve this problem using a more optimized method: the **Two-Pointer Approach**. This method allows us to merge the arrays in **O(n)** time without using extra space.

The idea is simple: since both arrays are already sorted, we can use two pointers to track the largest elements and merge from the end of `nums1`

. We compare the elements from the back of both arrays and place the larger one in the correct position in `nums1`

.

#### Steps:

1.Initialize three pointers:

`p1`

for the last valid element of`nums1`

(i.e.,`m - 1`

).`p2`

for the last element of`nums2`

(i.e.,`n - 1`

).`p`

for the last position of`nums1`

(i.e.,`m + n - 1`

).

2.**Compare elements** from the end of `nums1`

and `nums2`

, and place the larger element at the back of `nums1`

.

3.**Move pointers** accordingly and continue this process until all elements are merged.

###### Java Code:

```
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// Pointers for nums1, nums2, and the end of nums1
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
// Merge the arrays in reverse order
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
// If there are remaining elements in nums2, copy them over
while (p2 >= 0) {
nums1[p] = nums2[p2];
p--;
p2--;
}
}
}
```

##### Complexity:

- Time-Complexity: O(m+n) because we traverse each element in
`nums1`

and`nums2`

only once. - Space-Complexity: O(1) since we are merging the arrays in-place without using extra space.

##### Explanation:

- We start comparing elements from the back because the space at the end of
`nums1`

is unused. This ensures that we don’t overwrite elements we haven’t processed yet. - The
`while`

loop compares the elements of`nums1`

and`nums2`

and fills`nums1`

from the back, ensuring that it remains sorted. - If there are remaining elements in
`nums2`

after finishing the comparison, we copy them into`nums1`

.

This is the most efficient solution with a linear time complexity, making it optimal for larger datasets.

### Comparison of Approaches

Approach | Time Complexity | Space Complexity | Use Case |

Brute Force | O((m + n) log(m + n)) | O(m + n) | Simple, but inefficient for large inputs |

Two-Pointer | O(m + n) | O(1) | Optimal for large inputs |

### Conclusion

The **Two-Pointer Technique** is the best approach for solving merge sorted array problem, as it merges the two sorted arrays in linear time and without using extra space. The **Brute Force** approach, while easier to understand, is less efficient and impractical for larger datasets.