Merge Sorted Array

Merge one sorted array into another that has empty space at the end, without a second buffer. The trick is to fill from the back so nothing gets overwritten. Solve it below in Python or JavaScript, then read the walkthrough.

EasyArray Two Pointers Sorting Asked at 129 companies incl. Google, Amazon, Meta

Problem

You're given two integer arrays sorted in non-decreasing order, nums1 and nums2, and two integers m and n.

The first m elements of nums1 are real values. After them, nums1 has n extra slots filled with 0 as placeholders, so its total length is m + n. nums2 holds exactly n elements.

Merge nums2 into nums1 in place so that nums1 ends up holding all m + n values in sorted order. The function doesn't return anything; nums1 is checked after it runs.

Example 1

Input: nums1 = [2, 5, 9, 0, 0], m = 3, nums2 = [4, 7], n = 2
Output: [2, 4, 5, 7, 9]

The two trailing zeros are placeholders, not values to keep.

Example 2

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

nums1 has no real values, so the result is just nums2.

Example 3

Input: nums1 = [3, 8], m = 2, nums2 = [], n = 0
Output: [3, 8]

Constraints

nums1.length == m + n
nums2.length == n
0 ≤ m, n ≤ 200
1 ≤ m + n ≤ 200
-10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Merge Sorted Array in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Merge Sorted Array

Pattern: Two pointers from the back

The usual merge walks both arrays from the front and writes into a new array. Here the output has to go into nums1, and writing from the front would overwrite values of nums1 you haven't looked at yet.

The free space is at the end of nums1, so fill from the end. Compare the largest remaining values of each array (at m - 1 and n - 1) and write the bigger one into the last unfilled slot. The write position always stays at or ahead of the read position in nums1, because the slots between them are exactly the ones still owed to nums2. So nothing unread is ever overwritten.

Whenever an in-place problem has spare room at one end, ask whether working from that end removes the need for a buffer.

Approach 1: Copy in and sort

Write nums2 into the placeholder slots, then sort nums1. Short and correct, but it ignores that both inputs are already sorted.

Time O((m + n) log(m + n)) · Space O(1) to O(m + n), depending on the sort

Approach 2: Merge forward with a copy

Copy the first m values of nums1 into a temporary array, then run the standard front-to-back merge of that copy and nums2, writing into nums1. Linear time, but it needs m extra slots.

Time O(m + n) · Space O(m)

Approach 3: Merge backward in place

Keep three indices: i = m - 1 (last real value in nums1), j = n - 1 (last in nums2), and write = m + n - 1.

While j ≥ 0: if i ≥ 0 and nums1[i] > nums2[j], copy nums1[i] to write and move i left. Otherwise copy nums2[j] and move j left. Move write left either way.
When nums2 runs out, stop. Whatever is left of nums1 is already in its final place.

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

Approach	Time	Space
Copy in and sort	O((m + n) log(m + n))	O(1) to O(m + n), depending on the sort
Merge forward with a copy	O(m + n)	O(m)
Merge backward in place	O(m + n)	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Merge Sorted Array solution in Python

def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    i, j, write = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1

Merge Sorted Array solution in JavaScript

function merge(nums1, m, nums2, n) {
  let i = m - 1;
  let j = n - 1;
  let write = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[write--] = nums1[i--];
    } else {
      nums1[write--] = nums2[j--];
    }
  }
}

Common mistakes

Merging from the front in place, which overwrites values of nums1 before they are compared.
Looping while i ≥ 0 instead of while j ≥ 0. If nums1 runs out first, the remaining nums2 values never get copied.
Treating the placeholder zeros as real values. Only the first m entries of nums1 count.
Returning a new array instead of modifying nums1. Rebinding the parameter (nums1 = sorted(...)) also leaves the caller’s array unchanged.

What interviewers look for

Say why the front-to-back merge fails here before proposing the fix. The interviewer is listening for the insight that the empty space is at the end, so writing largest-first can never clobber unread data. A one-line argument for that (the gap between write and i is always exactly j + 1) is a strong signal.

Then call out the loop condition: you only need to keep going while nums2 has values left. Test it on m = 0 and on n = 0 before you finish.

Follow-up questions

What if nums1 had no extra space and you had to return a new array?

Use the standard front-to-back two-pointer merge into a fresh array of size m + n. It is the same O(m + n) work, with O(m + n) output space.

How would you merge k sorted arrays?

Put the first element of each array into a min-heap keyed by value and repeatedly pop the smallest, pushing the next element from the same array. That costs O(N log k) for N total elements. Merging the arrays pairwise in a tournament gets the same bound.

Can you merge two sorted halves of one array in place with O(1) extra space?

Yes, but it is much harder without spare room. Simple approaches use rotations and run in O(n²) worst case; linear-time in-place merging exists but is intricate. In practice, in-place merge sort usually accepts an O(n) buffer.

Companies that ask Merge Sorted Array

Merge Sorted Array is tagged by 129 companies in our interview dataset. The score shows how often it comes up at each company.

and 105 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Merge Sorted Array

EasyArray Two Pointers Sorting Asked at 129 companies incl. Google, Amazon, Meta

Problem

You're given two integer arrays sorted in non-decreasing order, nums1 and nums2, and two integers m and n.

The first m elements of nums1 are real values. After them, nums1 has n extra slots filled with 0 as placeholders, so its total length is m + n. nums2 holds exactly n elements.

Merge nums2 into nums1 in place so that nums1 ends up holding all m + n values in sorted order. The function doesn't return anything; nums1 is checked after it runs.

Example 1

Input: nums1 = [2, 5, 9, 0, 0], m = 3, nums2 = [4, 7], n = 2
Output: [2, 4, 5, 7, 9]

The two trailing zeros are placeholders, not values to keep.

Example 2

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

nums1 has no real values, so the result is just nums2.

Example 3

Input: nums1 = [3, 8], m = 2, nums2 = [], n = 0
Output: [3, 8]

Constraints

nums1.length == m + n
nums2.length == n
0 ≤ m, n ≤ 200
1 ≤ m + n ≤ 200
-10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Merge Sorted Array in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Merge Sorted Array

Pattern: Two pointers from the back

Whenever an in-place problem has spare room at one end, ask whether working from that end removes the need for a buffer.

Approach 1: Copy in and sort

Write nums2 into the placeholder slots, then sort nums1. Short and correct, but it ignores that both inputs are already sorted.

Time O((m + n) log(m + n)) · Space O(1) to O(m + n), depending on the sort

Approach 2: Merge forward with a copy

Copy the first m values of nums1 into a temporary array, then run the standard front-to-back merge of that copy and nums2, writing into nums1. Linear time, but it needs m extra slots.

Time O(m + n) · Space O(m)

Approach 3: Merge backward in place

Keep three indices: i = m - 1 (last real value in nums1), j = n - 1 (last in nums2), and write = m + n - 1.

While j ≥ 0: if i ≥ 0 and nums1[i] > nums2[j], copy nums1[i] to write and move i left. Otherwise copy nums2[j] and move j left. Move write left either way.
When nums2 runs out, stop. Whatever is left of nums1 is already in its final place.

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

Approach	Time	Space
Copy in and sort	O((m + n) log(m + n))	O(1) to O(m + n), depending on the sort
Merge forward with a copy	O(m + n)	O(m)
Merge backward in place	O(m + n)	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Merge Sorted Array solution in Python

def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    i, j, write = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1

Merge Sorted Array solution in JavaScript

function merge(nums1, m, nums2, n) {
  let i = m - 1;
  let j = n - 1;
  let write = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[write--] = nums1[i--];
    } else {
      nums1[write--] = nums2[j--];
    }
  }
}

Common mistakes

Merging from the front in place, which overwrites values of nums1 before they are compared.
Looping while i ≥ 0 instead of while j ≥ 0. If nums1 runs out first, the remaining nums2 values never get copied.
Treating the placeholder zeros as real values. Only the first m entries of nums1 count.
Returning a new array instead of modifying nums1. Rebinding the parameter (nums1 = sorted(...)) also leaves the caller’s array unchanged.

What interviewers look for

Then call out the loop condition: you only need to keep going while nums2 has values left. Test it on m = 0 and on n = 0 before you finish.

Follow-up questions

What if nums1 had no extra space and you had to return a new array?

Use the standard front-to-back two-pointer merge into a fresh array of size m + n. It is the same O(m + n) work, with O(m + n) output space.

How would you merge k sorted arrays?

Can you merge two sorted halves of one array in place with O(1) extra space?

Companies that ask Merge Sorted Array

Merge Sorted Array is tagged by 129 companies in our interview dataset. The score shows how often it comes up at each company.

and 105 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Merge Sorted Array

Approach 1: Copy in and sort

Approach 2: Merge forward with a copy

Approach 3: Merge backward in place

Solution code

Common mistakes

What interviewers look for

Follow-up questions

What if nums1 had no extra space and you had to return a new array?

How would you merge k sorted arrays?

Can you merge two sorted halves of one array in place with O(1) extra space?

Companies that ask Merge Sorted Array

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Merge Sorted Array

Approach 1: Copy in and sort

Approach 2: Merge forward with a copy

Approach 3: Merge backward in place

Solution code

Common mistakes

What interviewers look for

Follow-up questions

What if nums1 had no extra space and you had to return a new array?

How would you merge k sorted arrays?

Can you merge two sorted halves of one array in place with O(1) extra space?

Companies that ask Merge Sorted Array

Practice next

Get live help in the real interview