Skip to main content

8. Merge Sorted Array

easyAsked at Intuit

Merge two sorted arrays in-place. Intuit asks this because it mirrors reconciliation: merge two sorted transaction streams (bank + book) without allocating a third buffer.

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— QuickBooks reconciliation team screen, framed as merging bank + book transactions in-place.
  • Blind (2025-12)— Intuit phone-screen common warm-up.

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. nums1 has length m + n; the first m slots hold valid elements and the last n are 0 (placeholder).

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. Append + sort

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

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 sortedness — log-linear instead of linear. Acceptable but suboptimal.

2. Three-pointer from the back (optimal)

Walk three pointers from the right: tail of nums1 (m-1), tail of nums2 (n-1), and write position (m+n-1). Write the larger value into the write slot.

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: Linear, in-place. Walking from the back avoids overwriting unread nums1 values.

Intuit-specific tips

Intuit grades this on whether you spot the 'walk from the back' trick. Walking forward forces a buffer (or shifts) because you'd overwrite nums1 values you haven't read yet. Bonus signal: connect to a reconciliation merge where nums1 is the book ledger (with reserved tail slots) and nums2 is the day's bank feed.

Common mistakes

  • Walking from the front — clobbers nums1 values.
  • Forgetting the j >= 0 termination — once nums2 is exhausted, remaining nums1 values are already in place.
  • Off-by-one on k = m + n - 1 (writes past the end if you use m + n).

Follow-up questions

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

  • Merge K Sorted Arrays — heap-based.
  • Merge in-place across two streams with timestamps + amounts.
  • Merge two sorted bank feeds where ties broken by audit-ID.

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

The tail of nums1 is empty (placeholder 0s). Writing from the back uses those slots first, so you never overwrite an unread value.

What if nums1's tail isn't pre-allocated?

Then you need O(m+n) extra space, or you allocate a new array. The 'pre-allocated tail' is the trick that enables O(1) extra space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →