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:

1. Start from the End: Use a pointer last initialized to the end of nums1.

2. Compare and Place: Compare the last elements of nums1 and nums2. Place the larger one in the correct position (last) and decrement the pointers.

3. Fill Remaining Elements of nums2: If elements in nums2 remain after the comparison loop, copy them into nums1.

4. 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:

1. Start comparing the last elements: nums1[2] = 3 and nums2[2] = 6.

2. Place 6 at nums1[5].

3. Continue until all elements are merged.

Output:

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

---

Advantages of This Approach

1. In-Place Merging: No extra memory is used.

2. Efficient: The time complexity is linear, making it suitable for large arrays.

3. 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!