Merge Two Sorted Arrays

Merge two sorted arrays into a single sorted array in-place

Language Selection

Choose your preferred programming language

Showing: Python

Merge Two Sorted Arrays

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. 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.

Input/Output Specifications

Input:
- nums1 with length m + n where first m elements are valid
- nums2 with length n
- m and n representing valid elements count
Output: Modified nums1 containing merged sorted array

Constraints

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

Examples

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].

Example 2:

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

Example 3:

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

Solution Approaches

Approach 1: Two Pointers from End (Optimal)

Algorithm Explanation: Since we need to merge in-place and nums1 has extra space at the end, we can work backwards to avoid overwriting elements we haven’t processed yet.

Start from the end of both arrays
Compare elements and place the larger one at the end of nums1
Move pointers backwards
Continue until all elements are processed

Implementation:

Python:

def merge(nums1, m, nums2, n):
    """
    Merge two sorted arrays in-place using two pointers from end
    Time: O(m + n)
    Space: O(1)
    """
    # Start from the end
    i = m - 1  # Last element in nums1
    j = n - 1  # Last element in nums2
    k = m + n - 1  # Last position in nums1
    
    # Merge from the end
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # Copy remaining elements from nums2
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1
    
    # Remaining elements in nums1 are already in correct position

Java:

class Solution {
    /**
     * Merge two sorted arrays in-place using two pointers from end
     * Time: O(m + n)
     * Space: O(1)
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Start from the end
        int i = m - 1;  // Last element in nums1
        int j = n - 1;  // Last element in nums2
        int k = m + n - 1;  // Last position in nums1
        
        // Merge from the end
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
        
        // Copy remaining elements from nums2
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
        
        // Remaining elements in nums1 are already in correct position
    }
}

Go:

// merge - Merge two sorted arrays in-place using two pointers from end
// Time: O(m + n)
// Space: O(1)
func merge(nums1 []int, m int, nums2 []int, n int) {
    // Start from the end
    i := m - 1  // Last element in nums1
    j := n - 1  // Last element in nums2
    k := m + n - 1  // Last position in nums1
    
    // Merge from the end
    for i >= 0 && j >= 0 {
        if nums1[i] > nums2[j] {
            nums1[k] = nums1[i]
            i--
        } else {
            nums1[k] = nums2[j]
            j--
        }
        k--
    }
    
    // Copy remaining elements from nums2
    for j >= 0 {
        nums1[k] = nums2[j]
        j--
        k--
    }
    
    // Remaining elements in nums1 are already in correct position
}

JavaScript:

/**
 * Merge two sorted arrays in-place using two pointers from end
 * Time: O(m + n)
 * Space: O(1)
 */
function merge(nums1, m, nums2, n) {
    // Start from the end
    let i = m - 1;  // Last element in nums1
    let j = n - 1;  // Last element in nums2
    let k = m + n - 1;  // Last position in nums1
    
    // Merge from the end
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }
    
    // Copy remaining elements from nums2
    while (j >= 0) {
        nums1[k] = nums2[j];
        j--;
        k--;
    }
    
    // Remaining elements in nums1 are already in correct position
}

C#:

public class Solution {
    /// <summary>
    /// Merge two sorted arrays in-place using two pointers from end
    /// Time: O(m + n)
    /// Space: O(1)
    /// </summary>
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        // Start from the end
        int i = m - 1;  // Last element in nums1
        int j = n - 1;  // Last element in nums2
        int k = m + n - 1;  // Last position in nums1
        
        // Merge from the end
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
        
        // Copy remaining elements from nums2
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
        
        // Remaining elements in nums1 are already in correct position
    }
}

Complexity Analysis:

Time Complexity: O(m + n) - Each element is processed exactly once
Space Complexity: O(1) - Only using constant extra space

Trade-offs:

Optimal time and space complexity
Works in-place without additional memory
Intuitive once you understand the backward approach
Handles all edge cases naturally

Approach 2: Two Pointers from Start (Not Optimal)

Algorithm Explanation: Start from the beginning and merge elements, but this requires additional space to avoid overwriting.

Implementation:

Python:

def mergeFromStart(nums1, m, nums2, n):
    """
    Merge two sorted arrays using two pointers from start
    Time: O(m + n)
    Space: O(m) - violates space constraint
    """
    # Make a copy of nums1 to avoid overwriting
    nums1_copy = nums1[:m]
    
    i = j = k = 0
    
    # Merge elements
    while i < m and j < n:
        if nums1_copy[i] <= nums2[j]:
            nums1[k] = nums1_copy[i]
            i += 1
        else:
            nums1[k] = nums2[j]
            j += 1
        k += 1
    
    # Copy remaining elements
    while i < m:
        nums1[k] = nums1_copy[i]
        i += 1
        k += 1
    
    while j < n:
        nums1[k] = nums2[j]
        j += 1
        k += 1

Java:

class Solution {
    /**
     * Merge two sorted arrays using two pointers from start
     * Time: O(m + n)
     * Space: O(m) - violates space constraint
     */
    public void mergeFromStart(int[] nums1, int m, int[] nums2, int n) {
        // Make a copy of nums1 to avoid overwriting
        int[] nums1Copy = Arrays.copyOf(nums1, m);
        
        int i = 0, j = 0, k = 0;
        
        // Merge elements
        while (i < m && j < n) {
            if (nums1Copy[i] <= nums2[j]) {
                nums1[k] = nums1Copy[i];
                i++;
            } else {
                nums1[k] = nums2[j];
                j++;
            }
            k++;
        }
        
        // Copy remaining elements
        while (i < m) {
            nums1[k] = nums1Copy[i];
            i++;
            k++;
        }
        
        while (j < n) {
            nums1[k] = nums2[j];
            j++;
            k++;
        }
    }
}

Complexity Analysis:

Time Complexity: O(m + n) - Each element processed once
Space Complexity: O(m) - Requires additional space for copy

Trade-offs:

Simpler to understand
Violates O(1) space constraint
More intuitive forward approach
Not suitable for interview constraints

Approach 3: Using Built-in Functions (Not Optimal)

Algorithm Explanation: Use built-in sorting functions after copying elements.

Implementation:

Python:

def mergeBuiltin(nums1, m, nums2, n):
    """
    Merge using built-in functions
    Time: O((m + n) log(m + n))
    Space: O(1)
    """
    # Copy nums2 to the end of nums1
    for i in range(n):
        nums1[m + i] = nums2[i]
    
    # Sort the entire array
    nums1.sort()

Java:

class Solution {
    /**
     * Merge using built-in functions
     * Time: O((m + n) log(m + n))
     * Space: O(1)
     */
    public void mergeBuiltin(int[] nums1, int m, int[] nums2, int n) {
        // Copy nums2 to the end of nums1
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        
        // Sort the entire array
        Arrays.sort(nums1);
    }
}

Complexity Analysis:

Time Complexity: O((m + n) log(m + n)) - Sorting takes O(n log n)
Space Complexity: O(1) - In-place sorting

Trade-offs:

Very simple implementation
Higher time complexity
Doesn’t utilize the fact that arrays are already sorted
Not optimal for interview

Key Insights

Backward Merging: Working from the end avoids overwriting unprocessed elements
In-place Operation: The extra space at the end of nums1 enables in-place merging
Two Pointer Technique: Classic pattern for merging sorted arrays
Edge Case Handling: Empty arrays and single elements are handled naturally

Edge Cases

Empty nums2: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [], n = 0
Empty nums1: nums1 = [0,0,0], m = 0, nums2 = [1,2,3], n = 3
Single Elements: nums1 = [1,0], m = 1, nums2 = [2], n = 1
All Elements from nums2: nums1 = [0,0,0], m = 0, nums2 = [1,2,3], n = 3
Identical Arrays: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [1,2,3], n = 3

How Solutions Handle Edge Cases:

Empty arrays: Loops terminate naturally
Single elements: Direct comparison works correctly
All elements from one array: Remaining elements copied correctly
Identical arrays: Stable merge maintains order

Test Cases

def test_merge():
    # Test case 1
    nums1 = [1,2,3,0,0,0]
    merge(nums1, 3, [2,5,6], 3)
    assert nums1 == [1,2,2,3,5,6]
    
    # Test case 2 - empty nums2
    nums1 = [1,2,3,0,0,0]
    merge(nums1, 3, [], 0)
    assert nums1 == [1,2,3,0,0,0]
    
    # Test case 3 - empty nums1
    nums1 = [0,0,0]
    merge(nums1, 0, [1,2,3], 3)
    assert nums1 == [1,2,3]
    
    # Test case 4 - single elements
    nums1 = [1,0]
    merge(nums1, 1, [2], 1)
    assert nums1 == [1,2]
    
    # Test case 5 - identical arrays
    nums1 = [1,2,3,0,0,0]
    merge(nums1, 3, [1,2,3], 3)
    assert nums1 == [1,1,2,2,3,3]
    
    print("All tests passed!")

test_merge()

Follow-up Questions

Merge k Sorted Arrays: How would you merge k sorted arrays efficiently?
External Merge Sort: How would you merge two sorted files that don’t fit in memory?
Merge with Duplicates: What if you need to remove duplicates during merge?
Stable Merge: How would you ensure the merge is stable (preserves relative order)?
Merge Intervals: How would you merge overlapping intervals?

Common Mistakes

Overwriting Elements: Starting from the beginning without extra space
- Problem: Overwrites elements before they’re processed
- Solution: Work backwards or use extra space
Wrong Loop Conditions: Not handling remaining elements correctly
- Problem: Some elements not copied
- Solution: Add loops for remaining elements
Index Confusion: Mixing up m, n, and array lengths
- Problem: Array index out of bounds
- Solution: Carefully track valid element counts
Not Using Extra Space: Trying to merge from start without space
- Problem: Data loss during merge
- Solution: Use backward approach or allocate space

Interview Tips

Clarify Constraints: Ask about space limitations and in-place requirements
Start Simple: Begin with the extra space approach, then optimize
Draw Examples: Visualize the backward merging process
Handle Edge Cases: Discuss empty arrays and single elements
Discuss Trade-offs: Compare different approaches and their complexities

Concept Explanations

Two Pointer Technique: This problem demonstrates the classic two-pointer technique for merging sorted sequences. The key insight is using pointers to track positions in both arrays.

In-place Algorithms: Working backwards is a common pattern in in-place algorithms to avoid overwriting data that hasn’t been processed yet.

Merge Sort Foundation: This is the core operation in merge sort, making it fundamental to understanding divide-and-conquer sorting algorithms.