Skip to main content

8. Merge Sorted Array

easyAsked at Vercel

Merge two sorted arrays into one in-place, with the first array sized to hold both. Vercel asks this for the back-to-front two-pointer trick — relevant whenever they merge per-region cache hit/miss telemetry arrays without allocating.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel platform-engineering screen; back-to-front merge expected.
  • Blind (2026-Q1)— Reported in Vercel onsite recap with explicit 'no extra space' constraint.

Problem

You are given two sorted integer arrays nums1 and nums2 of sizes m and n respectively. Merge nums2 into nums1 as one sorted array. The number of elements initialized in nums1 are m. nums1 has a size of m + n; the last n slots are zero and should be ignored.

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. Concat and sort

Replace the zeros in nums1 with nums2's elements, then sort.

Time
O((m+n) log(m+n))
Space
O(1) extra
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: Wastes the fact that both inputs are sorted. Mention but pivot.

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

Start with pointers at the END of each meaningful range. Write the LARGER element to the back of nums1 and advance. This avoids overwriting unprocessed nums1 entries.

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: The 'merge from the back' insight is the whole point — going front-to-back would clobber unread nums1 entries. Only loop while j >= 0; remaining nums1 entries are already in place.

Vercel-specific tips

Vercel specifically watches for the back-to-front insight. If you try front-to-back, they'll ask 'what happens to the nums1 element you're about to read?' Bonus signal: explaining why only j needs to drive the loop (any leftover nums1 entries are already in their final positions).

Common mistakes

  • Looping while i >= 0 instead of j >= 0 — wastes work copying nums1 onto itself.
  • Forgetting the `i >= 0` guard inside the if — crashes when nums2 has elements smaller than every nums1 element.
  • Using a new array — passes the test but defeats the in-place requirement.

Follow-up questions

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

  • Merge k sorted arrays in-place (no extra space) — much harder.
  • Merge while preserving stability when values tie.
  • Online merge — what if nums2 is a stream and you don't know n?

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?

Front-to-back would overwrite a nums1 entry you haven't read yet. Back-to-front fills the trailing zeros first, so every write goes to a slot you've already consumed or never had real data in.

Why is the loop condition `j >= 0`?

If nums2 runs out, the remaining nums1 entries are already correctly placed (they were never overwritten and they're sorted). If nums1 runs out, you still need to drain nums2.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →