Skip to main content

9. Merge Sorted Array

easyAsked at Databricks

Merge two sorted arrays into the first one, in-place, where the first has trailing space to hold the result. Databricks uses this to test the back-to-front merge trick, which is the same memory-efficient pattern their sort-merge join uses.

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

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Glassdoor (2025-10)— Databricks shuffle-engineer screen — leads into spill-merge-on-disk discussion.
  • LeetCode Discuss (2026-Q1)— Tagged Databricks for the reverse-pointer pattern.

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 array should be stored inside nums1; nums1 has length m + n with the last n slots set to 0 to accommodate.

Constraints

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= 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. Concat + sort

Copy nums2 into nums1's tail, then 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-input invariant. Databricks penalizes this.

2. Three pointers from the end

Place the LARGEST element at the END. Pointers i, j walk from m-1 and n-1; write head k starts at m+n-1.

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(1) extra space. Working backwards avoids overwriting unread values in nums1.

Databricks-specific tips

Databricks grades the back-to-front insight specifically — this is the trick that lets an external merge sort spill to a single output buffer without an extra allocation. Be ready to extend to K-way merge during shuffle. The bonus signal is articulating WHY backwards works: forward merge requires extra space because writes would clobber unread elements in nums1.

Common mistakes

  • Walking forward and needing an extra buffer.
  • Forgetting the j >= 0 termination — if i runs out first, the remaining nums2 elements still need to be placed.
  • Stopping when i < 0 instead of j < 0 — if nums2 is empty, you're done; if nums1's original part is empty, you still have copying to do.

Follow-up questions

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

  • Merge K sorted arrays (LC 23 variant).
  • External merge sort: K-way merge with a heap.
  • What if nums1 had no trailing space? (You'd need a temporary buffer of size m.)

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 merge from the back?

The back of nums1 is unused space. Writing there doesn't overwrite any value you still need. Front-to-back would clobber unread elements.

Why is the j >= 0 loop condition correct?

If i runs out first, the remaining nums2 still needs to be placed in nums1 (which starts as 0s). If j runs out first, the remaining nums1 is already in the right slots.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →