Merge Sorted Array

Easy

📘 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 nums2 into nums1 as one sorted array.

• The final sorted array should not be returned by the function but instead be stored inside the array nums1.
• nums1 has a length of m + n, where the last n elements are set to 0 and should be ignored during the merge.

---

🔍 Example

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

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

---

🧠 Key Insight

• Since nums1 has enough space at the end, we can fill it from the back, comparing the largest unplaced elements of both arrays and placing the largest one at the current end.

• This avoids shifting elements unnecessarily.

🧮 Two Pointer Technique (from End)

Let’s define three pointers:

• p1 = m - 1 → last element in the real part of nums1

• p2 = n - 1 → last element in nums2

• p = m + n - 1 → last position in nums1 (to be filled)

🛠️ Solution

def merge(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    p = 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 nums2 is not exhausted
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

🕒 Time Complexity: \(O(m + n)\) -> Each element is processed exactly once.

📦 Space Complexity: \(O(1)\) -> We are doing in-place merge.

💡 Real-Life Analogy

Imagine two stacks of sorted papers, and you need to place them into a larger folder in sorted order. Starting from the largest paper in each pile, you insert the biggest one at the end of the folder, and keep doing this until all are placed.