# Question

Formatted question description: https://leetcode.ca/all/88.html

# 88. Merge Sorted Array

## Level

Easy

## Description

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:**

**Input:**

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6], n = 3

**Output:** [1,2,2,3,5,6]

## Solution

To avoid overwriting elements in `nums1`

before the elements are put in the correct positions, start from the end of the array and put elements to the correct positions backwards.

Let `index1`

and `index2`

be indices in original arrays `nums1`

and `nums2`

, and `index`

be the index in merged array `nums1`

. Initially, `index1 = m - 1`

, `index2 = n - 1`

and `index = m + n - 1`

.

While both `index1`

and `index2`

are greater than or equal to 0, each time compare the elements `nums1[index1]`

and `nums2[index2]`

, and put the greater elements to `nums1[index]`

. Reduce `index1`

by 1, and reduce either `index1`

or `index2`

by 1 where the element is put to `nums1[index]`

.

When only one array has remaining elements, put the elements from the array to the remaining positions in `nums1[index]`

.

2 pitfalls

- 1) Don’t use nums1.length if you give m, because nums1 is followed by a row of 0
- 2) Note that the pointer of p1 or p2 will be reduced to a negative number, then index error, so add a check

# Code

Java