Skip to main content

8. Merge Sorted Array

easyAsked at Electronic Arts

Merge nums2 into nums1 in place, exploiting trailing zero slots and walking from the back.

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

Problem

nums1 has length m+n with the first m valid slots and n trailing zeros; nums2 has n sorted values. Merge nums2 into nums1 in place so that nums1 is fully sorted.

Constraints

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

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=[1], m=1, nums2=[], n=0
Output
[1]

Approaches

1. Append and sort

Copy nums2 into nums1's tail, then sort.

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

Place the larger of nums1[i] and nums2[j] at the end and decrement; no element is overwritten before being read.

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:

Electronic Arts-specific tips

EA tooling teams deal with in-place merges of replay-event buffers, so the from-the-back pointer trick is the canonical answer they want to see.

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 Electronic Arts interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →