Merging two sorted arrays is a classic problem that has practical applications in many areas of computer science. It can be encountered in the context of sorting or as a step in more complex algorithms. In this article, we’ll tackle the problem of merging two sorted integer arrays, `nums1`

and `nums2`

, into a single array sorted in non-decreasing order.

## Table of Contents

## Problem Description: Merging Two Sorted Arrays

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`

, we are required to 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`

.

## Constraints

`nums1.length == m + n`

`nums2.length == n`

`0 <= m, n <= 200`

`-109 <= nums1[i], nums2[j] <= 109`

## Optimal Solution

Since both `nums1`

and `nums2`

are sorted, we can leverage this property to merge the arrays efficiently. We can start from the end of the arrays and merge them backward using three pointers to avoid overwriting elements in `nums1`

that haven’t been merged yet.

Here’s the concise code that merges the arrays optimally:

### Java Solution: Merging Two Sorted Arrays

```
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m-1; // Pointer for the end of nums1 (excluding zeros)
int j = n-1; // Pointer for the end of nums2
int k = m+n-1; // Pointer for the end of the result in nums1
// Merge elements from the end until one of the arrays is exhausted
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
// If there are any remaining elements in nums2, copy them to nums1
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
}
```

Certainly! Here’s the solution for the Merge Sorted Array problem translated into Python and Go.

### Python Solution: Merging Two Sorted Arrays

In Python, we can use the same logic of merging from the end, taking advantage of the fact that the input arrays are sorted.

```
class Solution:
def merge(self, nums1, m, nums2, n):
i, j, k = m - 1, n - 1, m + n - 1
# Merge elements from the end until one of the arrays is exhausted
while i >= 0 and j >= 0:
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
# If there are any remaining elements in nums2, copy them to nums1
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
```

### Go Solution: Merging Two Sorted Arrays

The same approach can be applied in Go, using the syntax specific to the language.

```
package main
func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
// Merge elements from the end until one of the arrays is exhausted
for i >= 0 && j >= 0 {
if nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
// If there are any remaining elements in nums2, copy them to nums1
for j >= 0 {
nums1[k] = nums2[j]
j--
k--
}
}
```

Both Python and Go solutions maintain the concise and optimal design, leveraging the fact that the input arrays are sorted.

## Analysis

This solution takes advantage of the fact that both input arrays are already sorted and utilizes the space available in `nums1`

, ensuring a space complexity of `O(1)`

. The time complexity is `O(m + n)`

, where `m`

and `n`

are the lengths of `nums1`

and `nums2`

, respectively.

## Conclusion: Merging Two Sorted Arrays

The Merge Sorted Array problem offers an elegant example of how understanding the properties of the given data can lead to an optimal and concise solution. By recognizing that the input arrays are sorted, we devised a solution that merges them in linear time and without the need for additional space. This example emphasizes the importance of analyzing constraints and leveraging inherent characteristics to derive an efficient algorithm. It’s a perfect showcase of the elegant and powerful coding practices that make the field of algorithms fascinating and intellectually stimulating.

Thank you for reading!

Dive into this insightful post on CodingReflex to unlock the power of Quarkus, Java’s revolutionary framework for building ultra-speed applications.

- For real-time updates and insights, follow our tech enthusiast and expert, Maulik, on Twitter.
- Explore a universe of knowledge, innovation, and growth on our homepage, your one-stop resource for everything tech-related.

For more information on related topics, check out the following articles: