Our cookbook, Love Real Food, is here! Get your copy ↣

# Coding Reflex # Merging Two Sorted Arrays: A Concise Solution

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.

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

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

• Explore a universe of knowledge, innovation, and growth on our homepage, your one-stop resource for everything tech-related. ### Toyota Joins Forces with Pony.ai to Manufacture Robotaxis in China

Autonomous vehicle development company Pony.ai is set to partner with Toyota with the ambitious aim of producing a fleet of “fully driverless robotaxis” for the Chinese market. The collaboration is expected to commence this year, backed by approximately \$139 million […] ### Getting Started: TypeScript Tutorial

TypeScript, a superset of JavaScript developed and maintained by Microsoft, has increasingly become a go-to choice for modern web development. It incorporates static types, classes, interfaces, and other powerful features that can make JavaScript development more robust and efficient. Introduction […]

### Popular now

• ### Writing Integration and Unit Tests for Your Spring Boot Project

Introduction If you’re working on a Spring Boot project that includes DTOs, models, service interfaces, service implementations, controllers, and JPA repositories, it’s crucial to write thorough integration and unit tests to ensure the quality and reliability of your code. In […]
• ### The Best Books on Go Lang: A Comprehensive Guide

Introduction If you are a programmer or aspiring to become one, you must have heard of Go Lang. Developed by Google, Go Lang has gained immense popularity for its simplicity, efficiency, and strong support for concurrent programming. Whether you are […]
• ### Is Data Structures and Algorithms (DSA) Required for Web Development?

When it comes to web development, there is often a debate about whether or not knowledge of Data Structures and Algorithms (DSA) is necessary. Some argue that DSA is an essential skill for web developers, while others believe that it […]

### Trending now

• 