Merge Sorted Array [Leet Code]

Problem

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.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

---

Code

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        for i in range(len(nums2)):
            nums1[len(nums1)-n+i] = nums2[i]
        nums1.sort()
        

Time Complexity:

The for loop iterates over the nums2 list, which has n elements. Therefore, the loop will run n times.
Inside the loop, assigning the values of nums2 to nums1 takes constant time O(1) for each iteration.
After the loop, the nums1 list is sorted using the built-in sort() method, which has a time complexity of O(m log m).
Combining these steps, the overall time complexity of the merge method is dominated by the sorting step, so it becomes O(m log m), where m is the size of nums1.

Space Complexity:

The space complexity of the merge method is mainly determined by any additional space used by the algorithm, excluding the input and output.
The algorithm doesn't use any additional data structures or arrays apart from the input nums1 and nums2.
Since the sorting operation is performed in-place, it doesn't require any additional space.
Thus, the space complexity of the merge method is O(1), indicating that it uses a constant amount of extra space.

---

Optimization

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2, p = m-1, n-1, m+n-1

        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

        # If there are remaining elements in nums2, copy them to nums1
        while p2 >= 0:
            nums1[p] = nums2[p2]
            p2 -= 1
            p -= 1

1. Initialize three pointers: p1 pointing to the last non-zero element in nums1, p2 pointing to the last element in nums2, and p pointing to the last position of the merged array in nums1.

2. Compare the elements at p1 and p2 positions in nums1 and nums2, respectively, and place the greater element at position p in nums1.

3. Decrement p1, p2, and p accordingly.

4. Repeat the process until either p1 or p2 becomes negative.

5. If there are remaining elements in nums2, copy them to nums1.

This optimized approach has a time complexity of O(m + n) and a space complexity of O(1), as it performs a single pass through both nums1 and nums2 without the need for sorting.