Faangprep Logo
Log inStart free
Browse curriculum

Merge Sorted Array

Merge two sorted arrays in place in O(m + n) by filling nums1 from the back with three pointers.

EasySolve on LeetCode

Problem Understanding

Merge Sorted Array: nums1 holds m sorted values followed by n zeros of room, and nums2 holds n sorted values. Merge nums2 into nums1 in place so nums1 ends up sorted.

Example: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3 becomes [1, 2, 2, 3, 5, 6].

The Intuition: The Free Space Is at the End

Merging from the front, as in Merge Two Sorted Lists, would overwrite nums1 values before they are placed. But the free room is at the end, and the end of the merged array holds the largest values. So merge backwards with two pointers and a write pointer:

  1. i at the last real nums1 value, j at the last nums2 value, k at the last slot.
  2. Write the larger of nums1[i] and nums2[j] to k, and move that pointer and k left.
  3. Stop when j < 0: whatever is left in nums1 is already in place.

k never passes i, because k − i = j + 1 > 0 while nums2 values remain, so nothing is overwritten too early.

Interactive Walkthrough

nums1's empty room is drawn dashed. Each step writes the larger of nums1[i] and nums2[j] into slot k, filling from the right. Watch the loop stop as soon as nums2 is used up.

Dry Run Table

Input: nums1 = [1, 2, 3, _, _, _], nums2 = [2, 5, 6]

i j k Compare Write
2 2 5 3 vs 6 6
2 1 4 3 vs 5 5
2 0 3 3 vs 2 3
1 0 2 2 vs 2 2 (from nums2)
1 −1 1 — stop

Result: [1, 2, 2, 3, 5, 6].

The Solution Template

Three pointers, merging from the back.

Merge Sorted Array Code
1var merge = function(nums1, m, nums2, n) {
2    let i = m - 1, j = n - 1, k = m + n - 1;
3    while (j >= 0) {
4        if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
5        else nums1[k--] = nums2[j--];
6    }
7};

Edge Cases & Common Mistakes

  • n = 0: nothing to merge; the loop never runs.
  • m = 0: every value comes from nums2; the i ≥ 0 check stops you reading nums1[−1].
  • Looping while i ≥ 0 instead of j ≥ 0: leftover nums2 values would never be copied.
  • Merging from the front: overwrites nums1 values that have not been placed yet.

Summary

nums1's free room is at the end, so merge backwards: compare the largest unplaced values of both arrays and write the larger to the last free slot. Stop when nums2 is used up. O(m + n) time, O(1) extra space.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Valid Palindrome

Next

Remove Duplicates from Sorted Array

The approach, step by step

  1. Point at the ends

    i = m − 1 (last nums1 value), j = n − 1 (last nums2 value), k = m + n − 1 (last slot).

  2. Place the larger value

    While j ≥ 0: if i ≥ 0 and nums1[i] > nums2[j], write nums1[i] to k and move i; otherwise write nums2[j] and move j. Move k.

  3. Stop when nums2 runs out

    The remaining nums1 values are already in place.

Frequently asked questions

Why fill nums1 from the back?

The empty room is at the end of nums1. Writing the largest values there first means the write position k is always at or after i, so no nums1 value is overwritten before it has been placed. Filling from the front would overwrite values you still need.

Why does the loop only run while j ≥ 0?

Once every nums2 value is placed, the nums1 values that are left are already at the front of nums1, in order. There is nothing left to move.

Can't I just append nums2 and sort?

That works in O((m + n) log(m + n)), but ignores that both arrays are already sorted. The three-pointer merge is O(m + n) and uses no extra space.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description