Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

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

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

👉 Link here to the repo to solve the problem

👌 Tips

If you simply consider one element each at a time from the two arrays and make a decision and proceed accordingly, you will arrive at the optimal solution.

You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don't know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?

Try moving from the end of the array to the beginning.

👊 Solution 1

This is a simple, yet inefficient solution. This would take M to copy the array onto nums1, and the O(N Log N) to sort the whole array.

This can be improved, as we are not really taking advantage that the arrays are already sorted.

public void badMerge(int[] nums1, int m, int[] nums2, int n) {
    int length = nums1.length - 1;
    while (n > 0) { // copy elements to the end of the array
        nums1[length] = nums2[n - 1];
        length--;
        n--;
    }
    Arrays.sort(nums1);
}

👊 Solution 2

Typically, one could achieve O(n+m) time complexity in a sorted array(s) with the help of two pointers approach.

In order to do this, we start appending at the end of the first array. We need one pointer for each one of them, whoever is the biggest we will append at the end.

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

we compare 6 with 3, 

6 > 3 ? add 6

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

5 > 3 ? add 5

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

2 > 3 ? add 3

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

And so on...

The code in Java:

public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) && (p2 >= 0))
        // compare two elements from nums1 and nums2
        // and add the largest one in nums1
        nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}

---

Question borrowed from “leetcode.com”