Merge Sorted Array

Problem You are given two sorted integer arrays: nums1 and nums2. The array nums1 has length m + n, where the first m values are meaningful sorted elements and the last n values are placeholder zeroes. The array nums2 has length n and is also sorted. Return the fully merged sorted array of length m + n. The judge checks the returned array, so you may mutate nums1 in place and return it, or build a new array and return that instead.

Input / output

• Input: nums1: int[], m: int, nums2: int[], n: int
• Output: int[], the merged sorted array of length m + n

Examples

1. nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 returns [1,2,2,3,5,6].
2. nums1 = [1], m = 1, nums2 = [], n = 0 returns [1].
3. nums1 = [0], m = 0, nums2 = [1], n = 1 returns [1].

Constraints

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[i] <= 10^9 for meaningful values
• The first m values in nums1 are sorted in non-decreasing order.
• nums2 is sorted in non-decreasing order.

Follow-up Can you solve it in O(m + n) time using only O(1) extra space by writing the merged result from the end of nums1 backward?