Merge Sorted Array

Difficulty: Easy
Topics: Array, Two Pointers, Sorting
Link: https://leetcode.com/problems/merge-sorted-array/

Problem Description

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.

Example 1:


Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:


Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:


Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

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

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Solution

1. Problem Deconstruction

Technical Definition

Given two sorted integer arrays nums1 (length m + n) and nums2 (length n), merge them into a single sorted array in non-decreasing order. The merged array must overwrite nums1, leveraging its trailing n zeros as buffer space. Constraints:

$0 \leq m, n \leq 200$
$1 \leq m + n \leq 200$
$-10^9 \leq \text{nums1}[i], \text{nums2}[j] \leq 10^9$

Beginner-Friendly Explanation

You have two sorted lists of numbers. Combine them into one sorted list without using extra space. The first list (nums1) has extra zeros at the end to make room for elements from the second list (nums2). Your goal is to fill nums1 with the merged sorted list.

Mathematical Formulation

Let:

$A = [a_0, a_1, \dots, a_{m-1}]$ (first $m$ elements of nums1)
$B = [b_0, b_1, \dots, b_{n-1}]$ (all elements of nums2)
Produce sorted array $C = [c_0, c_1, \dots, c_{m+n-1}]$ where $c_i \leq c_{i+1}$ for all $i$ , and $C$ is stored in nums1.

Constraint Analysis

$m + n \leq 200$ : Allows brute-force solutions but favors efficiency.
$m, n \geq 0$ : Handles empty arrays (e.g., m = 0 or n = 0).
Trailing zeros in nums1: Indicates in-place merging must avoid overwriting unprocessed elements.
Large value range ( $-10^9$ to $10^9$ ): Requires robust integer handling but no floating-point issues.

2. Intuition Scaffolding

Analogies

Real-World: Merging two sorted stacks of exam papers by always picking the top paper with the higher score.
Gaming: Combining two sorted loot lists in an RPG inventory without dropping items.
Mathematical: Merging two sorted sequences via pairwise comparisons, akin to the merge step in mergesort.

Common Pitfalls

Overwriting Critical Data: Merging front-to-back overwrites unprocessed values in nums1.
Ignoring Empty Arrays: Failing to handle cases where m = 0 or n = 0.
Pointer Errors: Incorrectly tracking indices when one array is exhausted.
Assuming Zero Initialization: Assuming trailing zeros in nums1 are always safe to overwrite (they are).
Unnecessary Complexity: Using O(m + n) extra space instead of in-place operations.

3. Approach Encyclopedia

Brute Force (Naive Merge with Extra Space)

Idea: Copy nums1’s valid elements to a temporary array, merge with nums2, and copy back.

Pseudocode:

temp = nums1[0:m]        # O(m) space  
i = j = k = 0  
while i < m and j < n:  
    if temp[i] <= nums2[j]:  
        nums1[k] = temp[i]  
        i += 1  
    else:  
        nums1[k] = nums2[j]  
        j += 1  
    k += 1  
# Copy remaining elements

Time Complexity: $O(m + n)$ (three passes).
Space Complexity: $O(m)$ (violates in-place requirement).

Optimal (Three-Pointer Reverse Merge)

Idea: Traverse backwards from the end of nums1, comparing the largest unmerged elements from nums1 and nums2.

Pseudocode:

i = m - 1   # Last valid element in nums1  
j = n - 1   # Last element in nums2  
k = m + n - 1   # Last index of nums1  
while j >= 0:  
    if i >= 0 and nums1[i] > nums2[j]:  
        nums1[k] = nums1[i]  
        i -= 1  
    else:  
        nums1[k] = nums2[j]  
        j -= 1  
    k -= 1

Time Complexity: $O(m + n)$ (single pass).
Space Complexity: $O(1)$ (in-place).

Visualization:

nums1: [1, 2, 3, 0, 0, 0]   nums2: [2, 5, 6]  
Step 0: i=2, j=2, k=5 → Compare 3 and 6 → Place 6 at k=5  
Step 1: i=2, j=1, k=4 → Compare 3 and 5 → Place 5 at k=4  
Step 2: i=2, j=0, k=3 → Compare 3 and 2 → Place 3 at k=3  
Step 3: i=1, j=0, k=2 → Compare 2 and 2 → Place 2 at k=2  
Step 4: i=1, j=-1, k=1 → Copy remaining nums1 elements (already in place)  
Result: [1, 2, 2, 3, 5, 6]

4. Code Deep Dive

Line-by-Line Annotations

def merge(nums1, m, nums2, n):  
    i = m - 1  # Pointer for last valid element in nums1  
    j = n - 1  # Pointer for last element in nums2  
    k = m + n - 1  # Pointer for last index of merged array  
  
    while j >= 0:  # Process all elements in nums2  
        if i >= 0 and nums1[i] > nums2[j]:  
            nums1[k] = nums1[i]  # Place larger element from nums1  
            i -= 1  
        else:  
            nums1[k] = nums2[j]  # Place larger element from nums2  
            j -= 1  
        k -= 1

Line 2–4: Initialize pointers to end of arrays.
Line 6: Loop until all nums2 elements are merged.
Line 7: Check if nums1 has elements left and if its current element is larger.
Line 8–9: Place nums1’s element and decrement i.
Line 10–11: Place nums2’s element and decrement j.
Line 12: Always decrement k.

Edge Case Handling

Example 2 (m=1, n=0): Loop condition j >= 0 fails immediately → no operation.
Example 3 (m=0, n=1): i = -1, so else branch always executes, copying nums2 into nums1.

5. Complexity War Room

Hardware-Aware Analysis

With $m + n \leq 200$ , the entire array fits in CPU L1 cache (typical size 32–64 KB). Pointers use negligible registers.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force (Extra Space)	$O(m + n)$	$O(m)$	High	❌ Fails in-place
Reverse Merge	$O(m + n)$	$O(1)$	Medium	✅ Optimal

6. Pro Mode Extras

Variants

LC 88 Follow-Up: What if nums1 has exactly $m$ $m$ elements and no extra space?
- Solution: Copy nums2 into nums1’s end first, then use standard merge.
LC 21: Merge two sorted linked lists (requires pointer manipulation).

Interview Cheat Sheet

Mention: Reverse merge avoids overwriting by leveraging unused space.
Watch For: Pointer arithmetic off-by-one errors.
Test: Empty arrays and equal elements.

Final Implementation:

def merge(nums1, m, nums2, n):  
    i, j, k = m - 1, n - 1, m + n - 1  
    while j >= 0:  
        if i >= 0 and nums1[i] > nums2[j]:  
            nums1[k] = nums1[i]  
            i -= 1  
        else:  
            nums1[k] = nums2[j]  
            j -= 1  
        k -= 1

#88 - Merge Sorted Array