AlgoViz
HomeArrays & Hashing

Merge two sorted arrays without extra space

Medium

Fill from the back, largest first

Problem

Given two integer arrays nums1 and nums2. Both arrays are sorted in non-decreasing order. Merge both the arrays into a single array sorted in non-decreasing order. The final sorted array should be stored inside the array nums1 and it should be done in-place. nums1 has a length of m + n, where the first m elements denote the elements of nums1 and rest are 0s. nums2 has a length of n.

In simple words

Compare from the end of the first and start of the second, swapping out-of-order pairs (gap method).

The idea

Write from the end of the combined space backwards, taking the larger of the two current tails each time. Because the tail of the first array is empty, writing backwards never overwrites a value that has not been read yet.

The trick

  • Three pointers: the tail of each input and the write position at the very end.
  • Any values left in the second array must still be copied; leftovers in the first are already in place.
  • O(n + m) time, O(1) extra space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

-5
-2
4
5
0
1
2
3

Step 1 of 2. Here's the example — nums1 = [-5, -2, 4, 5], nums2 = [-3, 1, 8] Values: -5, -2, 4, 5.

1/2
Optimal
timeO(n+m)spaceO(1)
1i = m-1, j = n-1, k = m+n-1     // nums1 = m reals + n zeros2while j >= 0:3  if i >= 0 and nums1[i] > nums2[j]:4    nums1[k--] = nums1[i--]5  else:6    nums1[k--] = nums2[j--]

Input

array
[-5, -2, 4, 5]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
a = [1, 4, 7, 8, 10], b = [2, 3, 9]
Output:
[1, 2, 3, 4, 7, 8, 9, 10]
Explanation:
The two arrays interleave into one sorted run.

Example 2

Input:
a = [1, 3], b = [2]
Output:
[1, 2, 3]
Explanation:
1,2,3.

Example 3

Input:
a = [5], b = [1]
Output:
[1, 5]
Explanation:
1,5.

Constraints

  • n == nums2.length.
  • m + n == nums1.length.
  • 0 <= n, m <= 1000
  • -10^4 <= nums1[i], nums2[i] <= 10^4
  • Both nums1 and nums2 are sorted in non-decreasing order.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.