Merge Sorted Array [LC150]

Hello friends,

Today we are going to solve another leetcode problem about merging sorred array. Link- https://leetcode.com/problems/merge-sorted-array/description/

You have two integer arrays, nums1 and nums2, which are sorted from smallest to largest. You also have two numbers, m and n, which show how many elements are in nums1 and nums2 respectively.

Your goal is to combine nums1 and nums2 into one single array that is also sorted from smallest to largest.

The merged array should go directly into nums1, which has enough space since its length is m + n. The first m elements of nums1 are for merging, while the last n elements, set to 0, can be ignored. The length of nums2 is 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] Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

Solution 1 (Brute):
TC:  O(m+n) + O(m+n), SC: O(m+n)
Code-
private static void DoMerge (int[] nums1, int m, int[] nums2, int n)
        {
            int[] num3 = new int[m + n];
            int left = 0;
            int right = 0;
            int idx = 0;

            while(left < m && right < n){
                if (nums1[left] <= nums2[right]){
                    num3[idx++] = nums1[left++];
                }
                else {
                    num3[idx++] = nums2[right++];
                }
            }

            while (left < m){
                num3[idx++] = nums1[left++];               
            }
            while (right < n){
                num3[idx++] = nums2[right++];               
            }

            //Print
            for (int i = 0; i<m+n; i++){
                if (i<m){
                    nums1[i] = num3[i];
                    Console.Write(nums1[i] + " ");
                }
                else
                {
                    nums2[i-m] = num3[i];
                    Console.Write(nums2[i-m] + " ");
                }
            }
        } 


Solution 2 (Better):
TC: O[min(m,n)] + O(m log m) + O(n log n), SC: O(1)

Code:
private static void DoMerge2 (int[] nums1, int m, int[] nums2, int n)
        {
            int left = m-1;
            int right = 0;

            while (left >= 0 && right < n){
                if (nums1[left] > nums2[right]){
                    (nums1[left], nums2[right]) = (nums2[right], nums1[left]); //swap the position
                    left--;
                    right++;
                }
                else {
                    break;
                }
            }
            Array.Sort(nums1);
            Array.Sort(nums2);

            //Print
            for (int i = 0; i<m; i++){               
                Console.Write(nums1[i] + " ");  
            }
            for (int i = 0; i<n; i++){               
                Console.Write(nums2[i] + " ");  
            }                
        }


Solution 3 (Optimal):
TC: log(m+n) * O(m+n), SC: O(1)

Code:
private static void DoMerge3 (int[] nums1, int m, int[] nums2, int n)
        {
            int len = m+n;
            int gap = (len/2) + (len%2);

            while (gap>0){
                int left = 0;
                int right = left+gap;
                while (right < len){                    
                    if (left < m && right >= m){ //nums1 and nums2
                        SwapIfGreater(nums1, nums2, left, right-m);
                    }
                    else if (right > m){ //nums2 and nums2
                        SwapIfGreater(nums2, nums2, left-m, right-m);
                    }
                    else{ //nums1 and nums1
                        SwapIfGreater(nums1, nums1, left, right);
                    }
                    left++;
                    right++;
                }
                if (gap==1){
                    break;
                }
                gap = (gap/2) + (gap%2);
            }

            //Print
            for (int i = 0; i<m; i++){               
                Console.Write(nums1[i] + " ");  
            }
            for (int i = 0; i<n; i++){               
                Console.Write(nums2[i] + " ");  
            }
        }

        private static void SwapIfGreater(int[] nums1, int[] nums2, int m, int n){
            if (nums1[m] > nums2[n]){
                (nums1[m], nums2[n]) = (nums2[n], nums1[m]); //swap the position
            }
        }

Hope you liked the article. Please share your comment/ suggestion.