8. Merge Sorted Array
easyAsked at VercelMerge 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 Sam K., 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 + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-10^9 <= nums1[i], nums2[j] <= 10^9
Examples
Example 1
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3[1,2,2,3,5,6]Example 2
nums1 = [1], m = 1, nums2 = [], n = 0[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.
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.