Merge Sorted Arrays — Backward Two Pointers

What does it solve?

Merge two sorted arrays into nums1, which has extra space at the end to hold both. Merging front-to-back would overwrite unread values, so the trick is to write from the back.

Key insight: put pointer i at the last real element of nums1, j at the last of nums2, and a write pointer k at the very end. Compare the two tails and drop the larger into slot k, then step that pointer back. The empty tail is always safe to overwrite → O(m+n) time, O(1) space.

The core idea

// write largest-first from the tail
i=m-1, j=n-1, k=m+n-1
while j >= 0:
  if i>=0 and nums1[i] > nums2[j]:
    nums1[k--] = nums1[i--]
  else:
    nums1[k--] = nums2[j--]

Complexity

Time complexity

O(m + n)

Each of the m + n elements is placed exactly once as the pointers march inward. No shifting, no re-sorting.

Space complexity

O(1)

Merged in place using nums1's reserved tail. Only three index variables, no auxiliary array.

Examples & edge cases

Live animation — fill nums1 from the back, largest first

i (nums1 tail) j (nums2 tail) k (write slot) placed

nums1 (m real + n empty slots) — merged in place

nums2 — source, read from the back

Current comparison

i = — j = — k = — placed = —

Step — of —

nums1[i]

—

left candidate

nums2[j]

—

right candidate

write slot k

—

back of nums1

placed

—

of m+n

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	j	k	compare	winner	wrote	placed

C++ implementation

merge_sorted_array.cpp

#include <bits/stdc++.h>
using namespace std;

// Merge nums2 into nums1 in place. nums1 has m reals + n empty slots.
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1;        // last real element of nums1
    int j = n - 1;        // last element of nums2
    int k = m + n - 1;    // last write slot

    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j])
            nums1[k--] = nums1[i--];   // nums1's tail wins
        else
            nums1[k--] = nums2[j--];   // nums2's tail wins
    }
    // leftover nums1 values are already in place
}

int main() {
    vector<int> nums1 = {1,2,3,0,0,0};
    vector<int> nums2 = {2,5,6};
    merge(nums1, 3, nums2, 3);
    for (int x : nums1) cout << x << " "; // 1 2 2 3 5 6
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars