# Problem

`Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3Output: [1,2,2,3,5,6]`
`Input: nums1 = [1], m = 1, nums2 = [], n = 0Output: [1]`
• `nums1.length == m + n`
• `nums2.length == n`
• `0 <= m, n <= 200`
• `1 <= m + n <= 200`
• `-109 <= nums1[i], nums2[i] <= 109`

# Approach 1 : Merge and sort

`var merge = function(nums1, m, nums2, n) {         for (let i = 0; i < n; i++) {            nums1[i + m] = nums2[i];        }        nums1.sort((a,b) => a-b);  };`
• Time complexity : O((n+m)log(n+m)).
• Space complexity : O(n), but it can vary.

## Approach 2 : Three Pointers (Start From the Beginning)Intuition

• Initialize `nums1Copy` to be a new array containing the first `m` values of `nums1`.
• Initialize read pointer `p1` to the beginning of `nums1Copy`.
• Initialize read pointer `p2` to the beginning of `nums2`.
• Initialize write pointer `p` to the beginning of `nums1`.
• While `p` is still within `nums1`:
• If `nums1Copy[p1]` exists and is less than or equal to `nums2[p2]`:
• Else — Write `nums2[p2]` into `nums1[p]`, and increment `p2` by `1`.
• Increment `p` by `1`.
`class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        // Make a copy of the first m elements of nums1.        int[] nums1Copy = new int[m];        for (int i = 0; i < m; i++) {            nums1Copy[i] = nums1[i];        }// Read pointers for nums1Copy and nums2 respectively.        int p1 = 0;        int p2 = 0;                        // Compare elements from nums1Copy and nums2 and write the smallest to nums1.        for (int p = 0; p < m + n; p++) {            // We also need to ensure that p1 and p2 aren't over the boundaries of their respective arrays.            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {                nums1[p] = nums1Copy[p1++];            } else {                nums1[p] = nums2[p2++];            }        }    }}`
• Time complexity : O(n+m).
• Space complexity :O(m).

## Approach 3 : Three Pointers (Start From the End)

`var merge = function(nums1, m, nums2, n) { 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--]   }else{    nums1[p] = nums2[p2--]  } }};//pointer 1 start at end of m//pointer 2 start at end of n//pointer 3 start at total length (minus 1 for index 0) aka end of list, and move left after each iteration//stop if we complete 2nd pointer values// if ( we run out of 1st pointer vals and val of nums at p1 is greater than nums2 at p2)//replace value of nums1 at p(pointer 3) with nums1[p1] then reduce p1 value// replace value of nums1 at p(pointer 3, end of list) with nums2[p2] then reduce p2 value`
• Time complexity : O(n+m).
• Space complexity : O(1).

# Conclusion

--

--

--

## More from SunJet Liu

Love podcasts or audiobooks? Learn on the go with our new app.