Skip to main content

8. Merge Sorted Array

easyAsked at N26

Merge two sorted arrays in-place into the first. N26 frames this as merging a new batch of cleared transactions into the running balance log.

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

Problem

You are given two sorted integer arrays nums1 and nums2, with the first having extra space at the end equal to nums2.length. Merge nums2 into nums1 as one sorted array in-place. The final result should be sorted ascending inside nums1.

Constraints

  • nums1.length == m + n
  • 0 <= m, n <= 200
  • Both inputs are sorted ascending

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 then sort

Copy nums2 into the 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. Two-pointer from back

Write the largest remaining value into the tail; avoids 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:

N26-specific tips

N26 grades for in-place writes — point out that the back-to-front pointer prevents clobbering, the same reason ledger inserts append at the tail.

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

Practice these live with InterviewChamp.AI →