Skip to main content

9. Merge Sorted Array

easyAsked at Datadog

Merge two sorted arrays in place, where the first has enough trailing space to hold both. Datadog uses this to test the reverse-iteration trick — the same backward-merge pattern they use when compacting two adjacent TSDB chunks without allocating a third buffer.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — interviewer specifically pushed for in-place no-extra-buffer.
  • Blind (2025-11)— Reported as a Datadog backend infra screen.

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 be stored inside nums1. nums1 has a length of m + n, where the last n elements are 0.

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

Copy nums2 into nums1's tail; call sort.

Time
O((m+n) log(m+n))
Space
O(1)
function merge(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 sorted invariant. Datadog interviewers will fail you for not exploiting input sortedness.

2. Backward two-pointer (optimal)

Fill nums1 from the END. Track i = m-1, j = n-1, k = m+n-1. Always write the larger of nums1[i] and nums2[j] at nums1[k].

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: O(m+n) time, O(1) extra space, no overwrites. The backward-walk avoids the 'I need to shift everything right' trap that breaks the forward approach.

Datadog-specific tips

Datadog interviewers will push you toward the backward approach by asking 'what if you can't allocate a temp buffer?' The key insight — write from the back so you never overwrite an unread element — is exactly how their TSDB compaction pass works on a memory-mapped block.

Common mistakes

  • Iterating forward and clobbering nums1's unread values — you'd need to shift elements right, killing the time complexity.
  • Forgetting that nums2 might exhaust first, leaving leftover nums1 — but that case is fine because nums1's left portion is already sorted in place.
  • Looping on i >= 0 instead of j >= 0 — if nums1's portion is exhausted first, you still need to drain nums2.

Follow-up questions

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

  • Merge K Sorted Arrays — min-heap variant (LC 23).
  • Merge Intervals (LC 56) — different shape but related two-pointer logic.
  • Sorted Array Median (LC 4) — uses partition-based merging.

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 iterate backward?

The free space is at the END of nums1. Writing backward fills that space first, so we never overwrite an element we still need to read.

What if nums1 runs out first?

Then nums2's remaining elements are smaller than everything already placed. The while(j >= 0) condition copies them; nums1's already-sorted prefix is untouched.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →