DSA SheetEasy
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Merge Sorted Array

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionwhy the empty suffix makes a backward merge possible

The first m positions of nums1 and all n positions of nums2 are sorted sequences; the zeros after position m - 1 are only empty storage. A normal merge chooses the smallest front value, but writing that value from the front would overwrite an element in nums1 that has not been compared yet.

The empty slots are at the end, so reverse the direction. Compare the largest valid value in each array and write the larger one into the last available slot. That write cannot destroy unread data: every unread value lies to its left. Once nums1's valid portion is exhausted, any remaining nums2 values can be copied into the beginning; if nums2 is exhausted first, nums1's remaining values are already in their final positions.

Two sorted arrays being merged from right to leftThe picture shows the valid sorted prefix of nums1 on the left, nums2 as a second sorted row below it, and an empty suffix at the right end of nums1. Pointer i sits on the last valid nums1 value, pointer j sits on the last nums2 value, and pointer k sits on the rightmost empty slot. The larger value at i or j is copied to k, then the used pointer and k move one position left. The picture makes clear that writing from the right protects every unread value.371215261114write 15nums1: valid sorted prefixfree suffix: empty slotsnums2: sorted valuesi ← moves leftk ← after each writej ← moves leftCompare from the right: write the largest remaining value into k; the unread prefix staysuntouched.

Approach

  1. Set i to m - 1, j to n - 1, and k to m + n - 1, because i and j must start at the ends of the actual sorted data while k starts at the final slot available for the merged result.
  2. While both i and j are valid, compare nums1[i] and nums2[j], because the larger of these two values is exactly the next value that belongs at the rightmost unfilled position.
  3. Write the larger value into nums1[k] and move k left, because each iteration fills one final position and must not leave the write pointer behind.
  4. Move i when nums1[i] is larger; otherwise move j, including ties, because the chosen value has been consumed and the other value remains available for a later position.
  5. Continue until one valid portion is empty, because no comparison is possible after that point and all positions to the right are already finalized.
  6. Copy nums2[j] through nums2[0] into the remaining slots while j is valid, because those values have not been written yet; if nums1 runs out, its remaining values already occupy the correct prefix.

Complexitylinear work and constant working memory

MEASUREBOUNDWHY
TimeO(m + n)Each valid value from nums1 and nums2 is examined at most once, and each value that must move is written once. The two pointers only move left, so no element is revisited by the merge.
SpaceO(1) extraOnly i, j, k, and a temporary comparison value use working memory. The modified nums1 array is required output and is excluded from the extra-space bound; the bound stays O(1) for every input shape, including when either valid portion is empty.
Here m is the number of valid values initially in nums1, and n is the number of values in nums2.

Annotated solutionC++ · in-place reverse merge · complete judge submission

CPPCompare the two valid suffixes and fill nums1 from its last slot toward the front.
#include <vector>

using namespace std;

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};

Common mistakestwo wrong code shapes that look plausible

Previous · Merge Two 2D Arrays by Summing Values