LeetCode Merge Sorted Array solution

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:

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

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

Solution

We can think of this problem as merging of two sorted arrays. I had studied the merge sort algorithm. So one approach could be to use recursion. But I thought of simpler approach. We can have two pointers, one pointing to beginning of array 1 and other pointing to beginning of array two. Now we can do a while loop and compare both elements and whichever is smaller we put that in a result array and increment that particular pointer only by one. We do that till we reach the end of either arrays. After that we copy rest of the elements of the array where we haven’t reached the end. Finally we copy this result array into array 1.

Below is the java code for the same.

 public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int[] result = new int[m+n];
        int i=0;
        int j=0;
        int index = 0;
        while (i<m && j<n) {
            if (nums1[i]<nums2[j]) {
                result[index++] = nums1[i];
                i++;
            }
            else {
                result[index++] = nums2[j];
                j++;
            }
        }
        
        while (i<m) {
            result[index++] = nums1[i++];
        }
        
        while (j<n) {
            result[index++] = nums2[j++];
        }
        
        for (int k=0; k<result.length; k++) {
            nums1[k] = result[k];
        }
    }

The time complexity of this would be O(m + n). And below is the Leetcode efficiency.

Two pointers approach is really helpful in solving sorting or merging kind of problems. In these kind of cases while loops can be a much better bet than for loops. Also we should give a thought on boundary cases, empty array cases, etc.