Skip to main content

88. Merge Sorted Array

easyAsked at Intel

Merge two sorted arrays in-place — nums1 has trailing zero slots reserved for nums2's elements. Intel asks because the trick (merge from the back so you never overwrite an unread element) is the same pattern that lets memmove handle overlapping regions safely in libc.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE phone-screen reports cite merge-sorted-array as a recurring two-pointer warm-up.
  • GeeksforGeeks (2025-09)— Intel Interview Experience archives reference the in-place + merge-from-back trick.
  • LeetCode discuss (2025-11)— Intel-tagged in the LC company-frequency listing.

Problem

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Constraints

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -10^9 <= nums1[i], nums2[j] <= 10^9

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]

Example 3

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

Approaches

1. Copy + sort (brute)

Copy nums2 into the tail of nums1 and sort the whole thing.

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

Tradeoff: Throws away the precondition that both inputs are already sorted. Use it as a one-liner reference but never as the final answer.

2. Two-pointer from front (works but needs extra space)

Standard merge using a third buffer, then copy back to nums1.

Time
O(m + n)
Space
O(m + n)
function mergeFront(nums1, m, nums2, n) {
  const merged = new Array(m + n);
  let i = 0, j = 0, k = 0;
  while (i < m && j < n) {
    if (nums1[i] <= nums2[j]) merged[k++] = nums1[i++];
    else merged[k++] = nums2[j++];
  }
  while (i < m) merged[k++] = nums1[i++];
  while (j < n) merged[k++] = nums2[j++];
  for (let x = 0; x < m + n; x++) nums1[x] = merged[x];
}

Tradeoff: Easy to write, but the extra buffer violates the spirit of the problem (the trailing zeros are explicitly reserved as workspace). Intel will push you to in-place.

3. Two-pointer from back (optimal)

Place largest elements first, writing into nums1's tail. Because we only OVERWRITE slots we've already 'read' (the trailing zeros), we never lose data.

Time
O(m + n)
Space
O(1)
function merge(nums1, m, nums2, n) {
  let i = m - 1;       // last real element of nums1
  let j = n - 1;       // last element of nums2
  let k = m + n - 1;   // write head, end of nums1
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[k--] = nums1[i--];
    } else {
      nums1[k--] = nums2[j--];
    }
  }
}

Tradeoff: Linear time, constant extra space, in-place. The trick: writing from the back guarantees the write head is always at or behind unread positions. Same invariant memmove relies on when handling overlapping ranges.

Intel-specific tips

Intel reviewers want the safety-of-overwrite argument articulated: 'Because I write into nums1's tail and the tail was reserved as zeros, every write happens into a slot I've already accounted for. The read head (i) can never collide with the write head (k) because k always advances at least as fast as i.' That sentence is the senior signal. The loop condition `while (j >= 0)` (not `while (j >= 0 && k >= 0)`) is a subtle correctness check — when nums2 is exhausted, nums1's remaining prefix is already in place.

Common mistakes

  • Looping from front and overwriting nums1[i] before reading it. Classic data-loss bug.
  • Using `i >= 0 && j >= 0` as the loop condition — when i hits -1, you still need to flush nums2 into nums1's head; the optimal loop only needs `j >= 0`.
  • Forgetting that m=0 is legal — initial nums1 is all zeros and must end up as nums2. The optimal loop handles this naturally.

Follow-up questions

An interviewer at Intel may pivot to one of these next:

  • Merge K sorted arrays (LC 23 / 88 generalized) — use a min-heap of size k.
  • What if both arrays are linked lists? (LC 21 Merge Two Sorted Lists — pointer-swap merge.)
  • What if nums1 didn't have reserved tail space? (Allocate a new array; no in-place option.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does merging from the back work in-place?

The write head sits in the reserved trailing slots. Every write goes into a slot whose 'value' is the placeholder zero. The read heads (i in nums1, j in nums2) only decrease, and the write head k always decreases at least as fast. So no live data is ever overwritten.

What if both arrays are huge and you can't fit them in cache?

The back-to-front merge is sequential in memory — perfect for streaming through cache lines from both inputs. Cache-friendly is the same property memcpy and memmove rely on for their fast paths.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →