Merge Sorted Array

Easy#88two arrays

You get two arrays sorted in ascending order. The first one ends with empty cells, exactly as many as there are numbers in the second. Merge the second array into the first, right inside it, so that the first stays sorted. Our example: [2, 5, 8, _, _, _] and [1, 6, 9] give [1, 2, 5, 6, 8, 9].

88 Merge Sorted ArrayWalkthrough · 1×

Example: nums1 = [2, 5, 8, _, _, _] and nums2 = [1, 6, 9]. Three pointers walk from the right: i over the numbers of nums1, j over nums2, write over the cells to fill.

nums2nums1011629021528345i
not placed yetcompared or movingjust writtenin its final placealready movedempty

i starts at the last number of nums1, 8

01/38
restart · back · play · step
Speed
1function merge(nums1, m, nums2, n):
2 i = m - 1
3 j = n - 1
4 write = m + n - 1
5 while j >= 0:
6 if i >= 0 and nums1[i] > nums2[j]:
7 nums1[write] = nums1[i]
8 i = i - 1
9 else:
10 nums1[write] = nums2[j]
11 j = j - 1
12 write = write - 1
13 return nums1
state
i
2
j
–
write
–
nums1
[2, 5, 8, _, _, _]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The largest number of all is the larger of the two last ones, and its place is the last cell. Then the same goes for the rest, so the result is filled from the end, one largest number at a time.
  2. Filling from the end never erases a number we still need: write is always to the right of i, so it lands only on an empty cell or on a number that has already moved.
  3. When nums2 runs out, the numbers left in nums1 are already in their places, so the loop stops there.

Complexity

Time O(m + n): each step puts one number in its place. Memory O(1): the merge happens inside nums1, without a third array.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.