Skip to main content

8. Merge Sorted Array

easyAsked at Adobe

Merge two sorted arrays where the first has trailing space to hold the merged result. Adobe asks this to test whether you'll spot the right-to-left trick that avoids overwriting unread data — a pattern that appears in scanline buffer compositing.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-Q1)— Adobe interviewers prize the right-to-left insight.
  • LeetCode Discuss (2025-09)— Common Adobe SDE phone 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 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. To accommodate this, 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]

Approaches

1. Concat and sort

Replace trailing zeros with nums2 and 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: Wastes the fact that both arrays are sorted. Adobe will dock you for this.

2. Right-to-left two pointers

Use three pointers — end of nums1's data (m-1), end of nums2 (n-1), end of total space (m+n-1). Fill from the back.

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 time, no extra space. The right-to-left direction is what makes the in-place merge safe — you never overwrite an element you haven't read yet. This is the exact pattern in scanline-composite right-to-left for occlusion.

Adobe-specific tips

The right-to-left insight is the entire point of this question for Adobe — they want to see if you recognize that going left-to-right would clobber nums1's unread values. Mention this directionality matters in scanline rendering when you're compositing back-to-front in a Z-buffer.

Common mistakes

  • Going left-to-right and shifting nums1's values — turns into O(m*n).
  • Forgetting the 'j >= 0' loop guard — if nums1 has leftover elements they're already in place; only nums2's leftovers need copying.
  • Off-by-one with k starting at m+n instead of m+n-1.

Follow-up questions

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

  • Merge K sorted arrays (LC 23).
  • Merge sorted linked lists (LC 21).
  • What if nums1 doesn't have trailing space?

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 is j >= 0 the only required condition?

If j hits -1, nums2 is exhausted and nums1's remaining elements are already in their correct positions. If i hits -1 first, the else branch copies nums2's leftovers correctly.

Could I use a separate buffer?

Yes, but it doubles memory. The right-to-left in-place merge is what Adobe asks for because it's the production technique for fixed-memory compositing pipelines.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →