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 + nnums2.length == n0 <= 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 -= 1Go 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:
