Merging Two Sorted Arrays In-Place : Leetcode Solution

Introduction

Merging two sorted arrays is a common programming problem, especially in scenarios where memory optimization is critical. This article presents a Python solution to merge two sorted arrays in-place using a two-pointer approach. The solution is efficient and adheres to the requirements of avoiding extra memory usage.

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. The initial numbers of elements in nums1 and nums2 are m and n, respectively.

The nums1 array has a size of m + n and contains m elements followed by n zeros, which are placeholders for the elements of nums2.

Approach

The solution leverages a two-pointer technique to traverse both arrays from the back, ensuring the largest elements are placed in the correct position. This avoids shifting elements unnecessarily.

Steps:

Start from the End: Use a pointer last initialized to the end of nums1.
Compare and Place: Compare the last elements of nums1 and nums2. Place the larger one in the correct position (last) and decrement the pointers.
Fill Remaining Elements of nums2: If elements in nums2 remain after the comparison loop, copy them into nums1.
Return the Result: The modified nums1 is the merged, sorted array.

Complexity

Time Complexity: $$O(m + n)$$
- Each element is processed once.
Space Complexity: $$O(1)$$
- The merging is done in-place with no additional space used.

Python Code

Below is the Python implementation:

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        last = m + n - 1

        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[last] = nums1[m-1]
                m -= 1
            else:
                nums1[last] = nums2[n-1]
                n -= 1

            last -= 1

        while n > 0:
            nums1[last] = nums2[n - 1]
            last, n = last - 1, n - 1

Example

Input:

nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3

Execution:

Start comparing the last elements: nums1[2] = 3 and nums2[2] = 6.
Place 6 at nums1[5].
Continue until all elements are merged.

Output:

[1, 2, 2, 3, 5, 6]

Advantages of This Approach

In-Place Merging: No extra memory is used.
Efficient: The time complexity is linear, making it suitable for large arrays.
Simple Logic: The two-pointer approach simplifies implementation and debugging.

Conclusion

The in-place merging of two sorted arrays is a practical example of the two-pointer technique. This solution is optimal in both time and space complexity, making it a go-to method for similar problems. Feel free to modify and extend this code for related scenarios, such as merging unsorted arrays.

Related Problems

Merge k Sorted Lists
Intersection of Two Arrays
Remove Duplicates from Sorted Array

Let’s Connect! If you found this article helpful, feel free to connect with me on LinkedIn and check out more of my articles on Hashnode!