Merge Sorted Array

Share

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:

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

Contents

Solution 1 - Start filling nums1 array from right side with higher elements

As per the problem statement, input arrays nums1 and nums2 are sorted, and nums1 array will have empty spots that can fit nums2 array, and m represents the length in nums1 array that has filled non empty numbers, and n represents nums2 length. Below is an example with nums1 = [4, 5, 6, 0, 0, 0] and nums2 = [1, 2, 3].

Example Now, we have to fill elements from nums2 into nums1 in sorted order.

So, in this approach, we will starting filling nums1 array from right side, with higher numbers from nums1 and nums2.

Implementation steps:
  • As a first step, We will create a variable last and initialize with last index of nums1 array, last = nums1.length -1; . We will also utilize inputs m and n as two pointers to point to nums1 and nums2 respectively.
  • Then, while m > 0 and n > 0, we will check the elements from nums1 and nums2 and copy the highest element to nums1 from right side. If we copy element from nums1, decrement m, or if we copy element from nums2, decrement n.
  • At the end, we may still have some elements in nums2, just like above example nums1 = [4, 5, 6, 0, 0, 0] and nums2 = [1, 2, 3], since nums1 have highest elements, we will copy all elements from nums1, and when we exit the while loop, we will have elements left in nums2, so we will simply copy all remaining elements from nums2.
Java
import java.util.Arrays;

public class MergeSortedArray {

    static void merge(int[] nums1, int m, int[] nums2, int n) {
        int last = nums1.length - 1;
        while(m>0 && n>0) {
            if(nums1[m-1] > nums2[n-1]) {
                nums1[last--] = nums1[m-1];
                m--;
            } else {
                nums1[last--] = nums2[n-1];
                n--;
            }
        }
        while(n>0) {
            nums1[last--] = nums2[n-1];
            n--;
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1));
        nums1 = new int[]{1};
        nums2 = new int[]{};
        merge(nums1, 1, nums2, 0);
        System.out.println(Arrays.toString(nums1));
        nums1 = new int[]{0};
        nums2 = new int[]{1};
        merge(nums1, 1, nums2, 1);
        System.out.println(Arrays.toString(nums1));
        nums1 = new int[]{4,5,6,0,0,0};
        nums2 = new int[]{1,2,3};
        merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1));

    }
}
Complexity Analysis:

Time complexity: Above code runs in O(m + n) time where m is the length of non-empty elements in nums1 array, and n is the length of nums2 array.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code