Merge Two Sorted Arrays (Two Pointer)

Problem Statement

Given two sorted arrays nums1 (with size m + n, where the last n slots are empty) and nums2 (size n), merge nums2 into nums1 so that nums1 stays sorted.

Example

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

Two Pointer Approach

Fill from the back. Keep a pointer at the last real element of each array and a write pointer at the end of nums1. Copy the larger value each step, so you never overwrite a value you still need.

Complexity

• Time: O(m + n)
• Space: O(1)

Solution Code

Python

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

Java

void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
        else nums1[k--] = nums2[j--];
    }
}

C++

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
        else nums1[k--] = nums2[j--];
    }
}

Key Takeaways

• Merging from the back is the trick that makes it O(1) space.
• The loop can stop once nums2 is exhausted.
• This is the merge step at the heart of merge sort.