88. Merge Sorted Array - Easy

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 the 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 the 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.

Constraints:
nums1.length === m + n

nums2.length == n

0 <= m, n <= 200

1 <= m + n <= 200

-10**9 <= nums1[i], nums2[j] <= 10**9

My approach:

Two pointer

We can start with two pointers i and j, initialised to m-1 and n-1, respectively. We will also have another pointer k initialised to m+n-1, which will keep track of the position in nums1 where we will be placing the larger element. Then we can start iterating from the end of the arrays i and j, and compare the elements at these positions. We will place the larger element in nums1 at position k, and decrement the corresponding pointer i or j accordingly. We will continue doing this until we have iterated through all the elements in nums2. If there are still elements left in nums1, we don't need to do anything because they are already in their correct place.

Complexity

Time complexity O(m+n) - We are iterating through both arrays once.

Space complexity O(1) - We are not using any extra space.

var merge = function(nums1, m, nums2, n) {

    let i = m - 1;

    let j = n - 1;

    let k = m + n -1;

    

    while (j >= 0) {

        if (i >= 0 && nums1[i] > nums2[j]) {

            nums1[k] = nums1[i];

            i--;

        else {

            nums1[k] = nums2[j];

            j--;

        }

            k--;

    }

};

Thoughts:
It's a bit confusing to follow the solution above. However, it is the most optimal because it's super fast and it doesn't use the built-in sort() method, which can be seen as cheating.  I will give my confidence that I understand the solution a 6/10, so I need to tackle similar problems and revisit them.