[Leetcode] Merge Sorted Array

88. Merge Sorted Array

You are given two integer arrays nums1and nums2, sorted in non-decreasing order, and two integers mand n, representing the number of elements in nums1and nums2respectively.

Merge nums1and nums2into 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, nums1has a length of m + n, where the first melements denote the elements that should be merged, and the last nelements are set to 0and should be ignored. nums2has 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

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

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

how to approach?

Merge and sort

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    for(let i=0;i<n;i++){
        nums1[i+m] = nums2[i]
    }
    nums1.sort((a,b)=>a-b)
};

1. set for loop using the elements number of nums2 which is n.
2. for nums1 index, add m since it's num1's element's length.
3. num1's i+m th element will be num2's i the element.
4. so now num1 has all the element of m+n, now sort it out using sort method

summary

Set the index of array and put the element using the index and sort it out.

But It's not taking advantage of the already sorted out array.

Three Pointers (Start From the Beginning)

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let nums1Copy: number[] = nums1.splice(0, m);
    let p1: number = 0;
    let p2: number = 0;

    for (let p = 0; p < m + n; p++) {
        if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
            nums1[p] = nums1Copy[p1];
            p1++
        } else {
            nums1[p] = nums2[p2];
            p2++
        }
    }
}

1. copy the nums1 using splice method.
2. set two pointers for nums1copy and nums2 array
3. use p pointer in for loop which is smaller than m+n.
4. when p2 is bigger than n or p1 is smaller than m and nums1copy element is smaller than nums2 element the nums1 p index element will be element from nums1copy. and the p1 poitner will increment by one.
5. other than that, nums1 p index element will be element from nums2 and the p2 will be incremented by one.
6. return nothing but nums1 is changed in the function.

summary

use 2 read pointers and 1 write pointer. no sort method is used so time complexity is managed as O(m+n)

Three pointers (start from the end)

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
        
    let p1 = m - 1;
    let p2 = n - 1;
    
    for (let p = m + n - 1; p >= 0; p--) {
        if (p2 < 0) {
            break;
        }
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--
        } else {
            nums1[p] = nums2[p2];
            p2--
        }
    }
    
}

1. set 2 pointers for nums1 and nums2, those start from each m and n
2. create for loop starts from the end of nums1 length as m+n-1 using p pointer
3. when p1 is bigger than 0 and nums1 element is bigger than nums2 element, nums1 element will be the p index's element in nums1. and p1 pointer decrement by one.
4. if not, nums2 element will be the element of nums1 p index's element. and p2 pointer decrement by one.
5. nums1 is changed as m+n-1 length array, no return

summary

use three pointers and starts from the end of the nums1 array, in this case, it doesn't use copy method so there is no other space used for this solution than the input to space complexity will be O(1).