Merging Two Sorted Arrays: A Concise Solution

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.

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: