Skip to content
LEETFLIX

Merge Sorted Array

EasyArrayTwo pointersSorting
Solve on LeetCode

Easy · merge into nums1 from the back. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 88. Merge Sorted Array. The copyrighted prompt is on LeetCode. This page is a working merge into nums1 from the back for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

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

Output

[1, 2, 2, 3, 5, 6]

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Fill nums1 from the right

The tail of nums1 is empty. Write the larger of the two remaining heads into the next empty slot, working right-to-left so you never overwrite an unread value.

Merging left-to-right would clobber unread values in nums1. The empty suffix is free space — use it.

Algorithm

  1. i = m−1, j = n−1, w = m+n−1.
  2. While both sides remain, write the larger into nums1[w] and decrement.
  3. Copy any leftover nums2 prefix.
Time
O(m + n)
Space
O(1)
Solution.py
class Solution:    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> list[int]:        i, j, w = m - 1, n - 1, m + n - 1        while j >= 0:            if i >= 0 and nums1[i] > nums2[j]:                nums1[w] = nums1[i]                i -= 1            else:                nums1[w] = nums2[j]                j -= 1            w -= 1        return nums1
Watch this run

03

Interactive walkthrough

Playing “Fill nums1 from the right”. Edit the input, hit Run, then scrub.

Approach: Fill nums1 from the right

Loading animation…