Reference: LeetCode

Difficulty: Easy

My Post: Java Solution with Clean Code (Two Pointers)

## Problem

Given two sorted integer arrays

`nums1`

and`nums2`

, merge`nums2`

into`nums1`

as one sorted array.

**Note:**

- 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 greater or equal to`m + n`

) to hold additional elements from`nums2`

.

**Example:**

1 | Input: |

**Follow up:** Can you solve in $O(N)$ without extra space?

## Analysis

### Merge and Sort

1 | public void merge(int[] nums1, int m, int[] nums2, int n) { |

**Time:** $O((m + n)\log{(m + n)})$**Space:** $O(1)$

### Two Pointers

Like merging two sorted linked list, we can loop over from the beginning of the array. It turns out that we need an extra array of size $m$.

We can start from the end of two arrays and append elements from the right side.

**Note:** Prefer `while-loop`

to `for-loop`

.

1 | public void merge(int[] nums1, int m, int[] nums2, int n) { |

**Time:** $O(m + n)$**Space:** $O(1)$