Leetcode — 88. Merge Sorted Array

The link to the problem: https://leetcode.com/problems/merge-sorted-array/

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
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 equal to m + n) to hold additional elements from nums2.

Constraints:

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

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

Thoughts:

From the problem description and the example shown above, we can see that this merge sorting should be done in-place. And that is not easy to think of how we can do it.

The problem will be a lot easier if we can just create a new array and keep assigning the smaller elements in nums1 and nums2 to our new array. Something like this : (the typical way to merge sort)

        int m = arr1.length, n = arr2.length;
        int i = 0, j = 0;
        int[] rst = new int[m+n];
        int k = 0;
        while(i<m && j<n)
        {
            if(arr1[i]<=arr2[j])
                rst[k++] = arr1[i++];
            else
                rst[k++] = arr2[j++];
        }
        while(i<m)
            rst[k++] = arr1[i++];
        while(j<n)
            rst[k++] = arr2[j++];
        return rst;

To do in-place, I think of several ways but none of them looks good.

One way to do it is to put all the numbers in nums2 to replace all the 0s in nums1 and sort the array again. It is also a bad solution since we should make good use of the knowledge — “nums1 and nums2 are sorted arrays”.

Another way is to keep comparing nums1 and nums2 like what we do in the above code. However, this will only work when all the numbers in nums1 are smaller than all the numbers in nums2. Otherwise, we need to handle the numbers in nums1 that being overridden by smaller numbers in nums2. It also requires a high time complexity if we keep moving the remaining numbers in nums1 backward so that they won’t be completely replaced.

Then I came up with an idea, why not traversing the arrays from backward to forward? So that we don’t need to worry about numbers in nums1 will be overridden and disappeared. (We already assigned the numbers to the end when we attempt to override the elements in nums1)

I use several graphs to illustrate my idea and we can see that this really works!

👉Goal: Merge [2,4,5,0,0,0] and [1,2,3] when m = 3, n = 3

Step 1. Initial State. i and j each points to the last element of nums1 and nums2. k is our pointer of “merged array”

1. All three pointers point to the end of the targeting array

Step 2. nums1[i] > nums2[j], we choose i over j.
i and k move forward, and j stays at the original position.

step 2 result

Step 3. nums1[i] > nums2[j], we choose i over j.
i and k move forward, and j stays at the original position.

step 3 result

Step 4. nums1[j] > nums2[i], we choose j this time.
j and k move forward, and i stays at the original position.

step 4 result

Step 5. We can choose either i or j since nums1[i] == nums2[j], depends on the algorithm we wrote. We choose j this time. j and k move forward, and i stays at the original position.

step 5 result

⚠️One thing happened here. We notice that this is the first time the element in nums1 is being overridden. However, there is no harm after that action because that number is already being assigned to the end of nums1.

Step 6. nums1[i] > nums2[j], we choose i over j.
i and k move forward, and j stays at the original position.

step 6 result

Step 7. We can’t compare nums1[i] and nums2[j] since one of them are out of bounds. We will just need to keep assigning the remaining elements to the remaining array.

Final Merged Array

Below is the 0ms code that beats 100% :

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

We can even skip the below loop since if we need to go in the loop, k and i point to the same element (try to think an example while [1,2,3,0,0,0] and [4,5,6] and you will know why):

while(i>=0)
    nums1[k--] = nums1[i--];

Time Complexity: O(n)
Space Complexity: O(1)