Merge Two Sorted Arrays Without Extra Space

MediumArraysTwo pointersSorting223 tests

You get two arrays of integers, a of length n and b of length m. Each one is sorted in ascending order.

Move the values between the two arrays so that:

a holds the n smallest values of both arrays, in ascending order, and
b holds the other m values, in ascending order.

The lengths of the arrays do not change. Return [a, b] after the change.

Note

The judge only checks the returned arrays. Return them; changing the input arrays in place is not enough.

Goal

Do it without a third array: use only O(1) extra memory besides a and b.

Hint: compare the largest value of a with the smallest value of b. While the first one is bigger, swap them and move one step inward on both sides. After that, every value in a is at most every value in b, and you only need to put each array back in order.

Examples

Example 1

Input:: [2,6,9,14], [1,5,11]
Output:: [[1,2,5,6],[9,11,14]]

All seven values in order are 1, 2, 5, 6, 9, 11, 14. The first four go to a and the last three go to b.

Example 2

Input:: [1,3], [4,8,12]
Output:: [[1,3],[4,8,12]]

Every value in a is already smaller than every value in b, so nothing moves.

Example 3

Input:: [7,7,20], [-4,7]
Output:: [[-4,7,7],[7,20]]

In order the values are -4, 7, 7, 7, 20. a gets the three smallest. The value 7 appears in both results, which is fine.

Constraints

1 <= n, m <= 15
-50 <= a[i], b[j] <= 50
a and b are each sorted in ascending order. Values can repeat.

Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.