Skip to main content

8. Merge Sorted Array

easyAsked at Snowflake

Merge nums2 into nums1 in-place, both sorted, with nums1 sized to hold both. Snowflake asks this because it's the canonical 'merge in place from the back' trick — and the same trick used in external sort-merge runs.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake execution-engine team uses this to set up external-merge follow-up.
  • LeetCode Discuss (2025-11)— Recurring at Snowflake new-grad screens.

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 a length of m + 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. Concatenate and sort

Copy nums2 onto 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 fact that both inputs are sorted. Don't ship in an external-merge engine.

2. Back-to-front two-pointer (optimal)

Three pointers: i at end of nums1 used data, j at end of nums2, k at end of nums1 buffer. Walk backward, placing 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: Linear, in-place. Filling from the back avoids overwriting nums1's unprocessed data — the same trick external-merge uses for in-place page merging.

Snowflake-specific tips

Snowflake interviewers grade this on whether you reach for the back-to-front merge immediately, or have to be prompted away from forward-merge with a copy. Bonus signal: connect to external sort-merge — when a sort run doesn't fit in memory, you read sorted pages from S3 and merge them via this exact pattern.

Common mistakes

  • Merging forward, which requires shifting elements (O(n) per insert).
  • Stopping the loop when i < 0 instead of j < 0 — but if nums2 has leftover elements you still need to copy them.
  • Forgetting that nums1 already has its data in [0, m) — you can't just zero out and merge.

Follow-up questions

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

  • Merge k sorted arrays (LC 23 generalization).
  • External merge sort — what if neither array fits in RAM?
  • How does Snowflake choose merge granularity (page size) for spilled sort runs?

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 back-to-front?

Forward-merge would overwrite nums1's unprocessed elements. Back-to-front writes into the empty buffer at the end, never colliding with what you still need to read.

When does Snowflake do external merge?

When a sort exceeds available memory, the engine spills sorted runs to S3, then streams them back through a k-way merge tree. The leaf merges are this 2-way pattern, scaled to k.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →