LeetCode: Merge Sorted Array

 Problem statement is copy pasted from leetcode as it is:

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]

Example 2:

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

 

Constraints:

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

My Solution:

package madwani.sushil.leetcode.Jan_8_15_2021;

public class MergeSortedArray {
    public static void main(String[] args) {
        int [] nums1 = new int[] {1, 2, 3, 0, 0, 0};
        int [] nums2 = new int[] {2, 5, 6};
        int [] nums12 = new int[] {1};
        int [] nums22 = new int[] {};
        int [] nums13 = new int[] {4,0,0,0,0,0};
        int [] nums23 = new int[] {1,2,3,5,6};
        int [] nums14 = new int[] {1,2,4,5,6,0};
        int [] nums24 = new int[] {3};
        int [] nums15 = new int[] {0,0,3,0,0,0,0,0,0};
        int [] nums25 = new int[] {-1,1,1,1,2,3};
        merge1(nums1, 3, nums2, 3);
        merge1(nums12, 1, nums22, 0);
        merge1(nums13, 1, nums23, 5);
        merge1(nums14, 5, nums24, 1);
        merge1(nums15, 3, nums25, 6);
        System.out.println("done");
    }

    // its a single pass with O(1) space complexity
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        m = m-1; // pointer to last element of num1
        n = n-1; // pointer to last element of num2

        // total number of elements
        int i = nums1.length - 1;

        // iterating from end of each array till we reach start of any array
        while ( n >= 0 && m >=0) {
            if (nums2[n] > nums1[m]) {
                nums1[i--] = nums2[n--];
            } else {
                nums1[i--] = nums1[m--];
            }
        }
        // if second array is still left with the elements
        while (n >= 0) {
            nums1[i--] = nums2[n--];
        }
    }

    // with space complexity O(N)
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if ( n == 0) {
            return;
        }
        int i =0, j=0;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) i++;
            else {
                insert(nums1, i, nums2[j]);
                m++;
                j++;
            }
        }
        while (i < nums1.length && j < n) {
            if (nums1[i] !=0) i++;
            else nums1[i++] = nums2[j++];
        }

    }

    public static void insert(int[] nums1, int position, int tNum) {
        while (position < nums1.length) {
           int temp = nums1[position];
           nums1[position++] = tNum;
           tNum = temp;
        }
    }
}