Skip to main content

8. Merge Sorted Array

easyAsked at Plaid

Merge two sorted arrays in-place, where the first has extra trailing space to hold the second. Plaid asks this because merging a new batch of transactions into a pre-allocated buffer is a hot path in their ingestion code.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE I onsite.
  • Blind (2026)— Reported as Plaid backend 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 each. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should be stored inside the array nums1, which has length m + n with trailing zeros.

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]

Approaches

1. Copy nums2 in, then sort

Overwrite the trailing zeros with nums2, then sort the whole thing.

Time
O((m+n) log(m+n))
Space
O(1) or O(log n) sort stack
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 precondition. Don't ship this in a Plaid interview.

2. Two-pointer fill from the back

Walk both arrays from the largest element down, writing into nums1's tail. No risk of overwriting unread data because the tail is exactly the right size.

Time
O(m+n)
Space
O(1)
function merge(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, w = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[w--] = nums1[i--];
    } else {
      nums1[w--] = nums2[j--];
    }
  }
}

Tradeoff: The fill-from-the-back trick avoids the need for an auxiliary buffer. Note that you only need to loop while j >= 0 — when nums2 is drained, the rest of nums1 is already correctly positioned.

Plaid-specific tips

Plaid loves the back-fill trick because it shows you can reason about read/write pointer collision. Bonus signal: explicitly state the invariant 'write pointer w is always >= read pointers i and j, so we never overwrite unread data.' That phrasing maps directly to their in-place ETL transforms.

Common mistakes

  • Filling from the front — overwrites unread elements in nums1.
  • Looping while i >= 0 || j >= 0 — wastes work when nums1's prefix is already in place.
  • Forgetting that when j drains first, nums1 is done — but when i drains first, you must still copy the rest of nums2.

Follow-up questions

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

  • Merge k sorted arrays in-place into a pre-allocated buffer.
  • What if the trailing zeros are not exactly n slots — handle resize.
  • Stream version where nums2 arrives over the network in chunks.

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 fill from the back, not the front?

Filling from the front would overwrite unread nums1 elements. Filling from the back guarantees the write pointer is always to the right of both read pointers, so unread data is safe.

What if nums1 still has unread elements when nums2 is drained?

They're already in correct sorted position — no work needed. That's why the loop only checks j >= 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →