Merge Sorted Array

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given two arrays in sorted order, merge them into one, in place
• Put elements from both arrays into array1

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Input arrays are sorted
• Need to solve it in $O(m+n)$ or linear time
• Whenever given a sorted array and you have to put items in place, its probably best to think about going from end to start or bigger to smaller

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Use Two Pointers to track which element is greater
• Use another pointer to track where to the element

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Two Pointers

Time & Space Complexity

• Time: $O(m+n)$ → Reason: We iterate through each item on both input array once
• Space: $O(1)$ → Reason: No extra space used

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.
        """
        p1, p2, p3 = m - 1, n - 1, m + n - 1

        while p3 >= 0:
            num1 = nums1[p1] if p1 >= 0 else -inf
            num2 = nums2[p2] if p2 >= 0 else -inf

            if num1 >= num2:
                nums1[p3] = num1
                p1 -= 1
            else:
                nums1[p3] = num2
                p2 -= 1
            p3 -= 1

Common Mistakes / Things I Got Stuck On

• Cannot start or merge array from start to end