DSAPrep
EasyTwo Pointers

Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1

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

            
                Explanation: We are merging [1,2,3] and [2,5,6]. The result [1,2,2,3,5,6] is stored back into nums1, with the trailing zeros of nums1 used as scratch space for the merge.

Example 2

            Input: nums1 = [1], m = 1, nums2 = [], n = 0
            Output: [1]
            

            
                Explanation: We are merging [1] and []. nums1 already holds the correct answer, so no writes are needed.

Example 3

            Input: nums1 = [0], m = 0, nums2 = [1], n = 1
            Output: [1]
            

            
                Explanation: Because m = 0, nums1 has no real elements; the 0 only exists so the merged result can fit. The single nums2 value 1 is written into slot 0, giving [1].

Constraints

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -10^9 <= nums1[i], nums2[j] <= 10^9
Follow-up: Can you come up with an algorithm that runs in O(m + n) time?
View original on LeetCode ↗

The pattern behind this problem is the backward fill. nums1 is not a clean input array — its real m values are followed by n zeros that exist only to give the merged result room, and those zeros sit exactly where the largest merged values must go. So instead of merging left to right (which would force every unused value to be shoved sideways), we merge from the end: two read pointers walk the largest unused value of each array, and one write pointer drops the bigger of the two into the rearmost open slot, descending toward the front. Filling backward means every slot we write is a trailing cell we were allowed to overwrite, so a not-yet-merged value is never clobbered — and when one array runs out, whatever of the other remains at the front is already in its final position.

Brute Force: Copy and Sort

Time O((m+n) log(m+n))Space O(1)

The direct interpretation of the problem: splice nums2 over the trailing zeros of nums1, then sort the whole array. It respects the in-place contract — the answer still ends up inside nums1 — and it is trivially correct because sorting guarantees the non-decreasing order. The cost is re-sorting the entire m + n array even though both halves were already individually sorted, throwing away all the ordering information the inputs already give us.

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        # Drop every nums2 value over the trailing zeros, then sort everything.
        for j in range(n):
            nums1[m + j] = nums2[j]
        nums1.sort()

Why it is linearithmic: after copying, the merge becomes a full sort of an m + n element array, which costs O((m + n) log(m + n)) in the worst case. That is strictly worse than the O(m + n) a linear merge achieves because we re-sort data that was already sorted. Space stays O(1): the sort runs in place and the copy only fills cells we were allowed to write.

Two Pointers: Backward Fill

OptimalTime O(m+n)Space O(1)

Model the merge like a standard merge of two sorted lists, but run it backward. Keep p1 on the largest unused value of nums1 (starting at m - 1), p2 on the largest unused value of nums2 (starting at n - 1), and p on the next write slot (starting at m + n - 1). At every step compare the two candidates, place the bigger one at p, and move that side’s read pointer plus p one slot left. Stop as soon as p2 goes negative — at that point every nums2 value has been placed, and whatever real nums1 values remain at the front were already in their correct positions. The p1 >= 0 guard keeps nums1[0] from being misread as a candidate once its real values are exhausted.

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        # p1, p2 read the largest unused value of each array; p writes.
        p1, p2, p = m - 1, n - 1, m + n - 1
        while p2 >= 0:
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1

Watch the backward fill on the worked example, nums1 = [1,2,3,0,0,0] with nums2 = [2,5,6]: p1 and p2 pick the largest unused value of each array, and p drops the winner into the rearmost open slot.

start
nums2
20
51
62
▲ p2
nums1
10
21
32
▲ p1
03
04
05
▲ p

p1 and p2 pick the largest unused value of each array; p fills nums1 from the back — so every write lands in a trailing slot we were allowed to overwrite, never on top of a real value still waiting to be merged

1 / 10
currentseencomparingresult

Why fill from the right? nums1 already has room: its last n cells are zeros we are allowed to destroy, and those zeros sit exactly where the largest merged values will land. Write backwards and every slot we fill is one we may overwrite, so we never clobber a real value we still need. p1 and p2 point at the largest unused value of each array (the real ends), and p marks the next write slot at the very back.

Watch the leftover case, nums1 = [1,2,3,0] with nums2 = [1]: once nums2 runs out, the remaining 1 in front of nums1 is already correct, so the merge simply stops instead of copying anything extra.

start
nums2
10
▲ p2
nums1
10
21
32
▲ p1
03
▲ p

p1 and p2 pick the largest unused value of each array; p fills nums1 from the back — so every write lands in a trailing slot we were allowed to overwrite, never on top of a real value still waiting to be merged

1 / 8
currentseencomparingresult

A second trace showing the leftover case. nums1 = [1,2,3,0] with m = 3 holds one spare zero; nums2 = [1] has a single element. p1 = 2, p2 = 0, p = 3.

Why it is linear: each of the m + n slots is written exactly once, and each pointer moves only leftward, so the loop runs at most m + n iterations — O(m + n) time. Space is O(1) because everything happens on nums1 itself. Why it never clobbers a live value: because the fill runs right to left, any slot we write is strictly to the right of every real value still waiting in nums1 once that real value is decided; a value not yet merged is never in a slot we are about to overwrite. Why we stop early: once p2 is below zero, every nums2 element has been placed, and the untouched prefix of nums1 already occupied its correct front slots, so copying the rest would be redundant. The p1 >= 0 guard handles the m = 0 edge case (example 3): with no real nums1 values, every slot is filled straight from nums2.