Skip to main content

8. Merge Sorted Array

easyAsked at Quora

Merge two sorted arrays in place where the first has extra slots at the end.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given two sorted integer arrays nums1 (size m+n with the last n slots as zero) and nums2 (size n). Merge nums2 into nums1 so nums1 ends sorted, modifying nums1 in place.

Constraints

  • 0 <= m, n <= 200
  • nums1.length == m + n
  • nums2.length == n

Examples

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]

Example 2

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

Approaches

1. Concat and sort

Copy nums2 into the tail then sort the whole thing.

Time
O((m+n) log (m+n))
Space
O(1)
for (let i = 0; i < n; i++) nums1[m+i] = nums2[i];
nums1.sort((a,b)=>a-b);

Tradeoff:

2. Three pointers from the back

Fill nums1 from the right with the larger of the two tails to avoid overwrites.

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

Tradeoff:

Quora-specific tips

Quora reaches for back-to-front merges because their answer ranker merges new candidate batches into a preallocated top-K buffer without resizing.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Merge Sorted Array and other Quora interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →