🚀 I’m kick-starting a new LeetCode Solutions Series, where I’ll break down coding problems step by step, explaining the logic and best approaches! Stay tuned for more solutions. Now, let’s dive into our first problem!

Problem Statement

You are 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 respectively.

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.

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

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

Approach: Two Pointers from the End

Idea

Instead of merging from the beginning, we can merge from the end of nums1 to efficiently place the largest elements in the correct position. This avoids the need for extra space.

Algorithm

1. Use three pointers:
   • p1 at the last non-zero element in nums1 (m - 1)
   • p2 at the last element in nums2 (n - 1)
   • p at the last index of nums1 (m + n - 1)
2. Compare elements from nums1 and nums2, placing the larger one at index p.
3. Move the pointers accordingly.
4. If any elements remain in nums2, copy them to nums1.

class Solution:
    def merge(self, nums1, m, nums2, n):
        p1, p2, p = m - 1, n - 1, m + n - 1

        # Merge from the back
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1

        # Copy remaining elements from nums2 if any
        while p2 >= 0:
            nums1[p] = nums2[p2]
            p2 -= 1
            p -= 1

Step-by-Step Execution

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

nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
Pointers: p1 = 2, p2 = 2, p = 5

Step 1: Compare nums1[2] = 3 and nums2[2] = 6

• 6 > 3, place 6 at nums1[5]
• Move p2 = 1, p = 4

nums1 = [1, 2, 3, 0, 0, 6]

Step 2: Compare nums1[2] = 3 and nums2[1] = 5

• 5 > 3, place 5 at nums1[4]
• Move p2 = 0, p = 3

nums1 = [1, 2, 3, 0, 5, 6]

Step 3: Compare nums1[2] = 3 and nums2[0] = 2

• 3 > 2, place 3 at nums1[3]
• Move p1 = 1, p = 2

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

Step 4: Compare nums1[1] = 2 and nums2[0] = 2

• 2 == 2, place 2 from nums2 at nums1[2]
• Move p2 = -1, p = 1

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

Step 5: nums2 is exhausted, so we are done.

Time and Space Complexity

• Time Complexity: O(m + n) since each element is processed once.
• Space Complexity: O(1), as we modify nums1 in place without extra space.

Conclusion

The two-pointer approach provides an efficient way to merge two sorted arrays in-place without using extra space. This method is optimal and is commonly used in similar merging problems.

🚀 Stay tuned for more LeetCode solutions in this blog series!