LeetCode — Merge Sorted Array

Problem Link: https://leetcode.com/problems/merge-sorted-array/

Photo by pine watt on Unsplash

Problem Description: 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.

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]

Approach Used: Merge function of Merge Sort

Explanation: In this question, we have to merge both the arrays into a single array and that array should be input array 1. Now one simple way to do this would be to simply combine the two arrays and run a sort. Another way would be to add the element as we do in insertion sort. The benefits of these methods are that we do not require any extra space. But the downside of the algorithms is that they require a minimum of O(nlogn) time.
The approach we will use does it in O(n) time and O(n) space. We will run a loop on both arrays simultaneously and compare current elements. We will add the smaller element to output array and move one step ahead in the same array. We will continue this until one of the arrays gets exhausted. At this point, we will simply add all the elements of the other array at the back because they are already sorted. Since the output has to be input array 1 always, we will copy our output array to input array 1.

Code: (Java)

public void merge(int[] nums1, int m, int[] nums2, int n) {
        //variables to run loop on nums1 and nums2 respectively
        int i=0, j=0;
        //output array - size will be total size of nums1 and nums2
        int[] nums3 = new int[m+n];
        //to know current index in nums3 where new element will be placed
        int k=0;
        
        while(i<m && j<n){
            //if element of num1 is smaller add it to output and increment only in num1
            if(nums1[i]<nums2[j]){
                nums3[k] = nums1[i];
                i++;
            }
            //if element of num2 is smaller add it to output and increment only in num2
            else{
                nums3[k] = nums2[j];
                j++;
            }
            //since element is added at current index, we move to next index
            k++;
        }
        //only of the two loops written below will run
        //because one list would be completed by above loop
        
        while(i<m){
            nums3[k] = nums1[i];
            i++;
            k++;
        }
        while(j<n){
            nums3[k] = nums2[j];
            j++;
            k++;
        }
        
        //copying all the elements back to nums1
        for(i=0; i<nums3.length; i++){
            nums1[i] = nums3[i];
        }
    }

Complexity:
Space complexity : O(m+n). The output array is of size m+n.
Time complexity: O(m+n). We will visit all the elements of both the arrays exactly once.
Here m and n are the lengths of array 1 and array 2 respectively.