Skip to main content

8. Merge Sorted Array

easyAsked at PayPal

Merge two sorted arrays in-place into the first one (which has buffer space at the end). PayPal asks this to test reverse-pointer thinking — the same approach they use when interleaving an authorized-transactions buffer with a capture-events buffer for end-of-day reconciliation.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • LeetCode Discuss (2026-01)— PayPal backend phone screen, follow-up to Merge Two Sorted Lists.

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, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 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

Copy nums2 into nums1 (overwriting zeros), 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: O((m+n) log(m+n)) ignores the precondition that both arrays are already sorted.

2. Reverse two-pointer (optimal)

Fill from the end. Pointers at nums1[m-1], nums2[n-1], write pointer at nums1[m+n-1]. Always write the larger.

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: Backward fill avoids overwriting unread nums1 elements. Same pattern as PayPal's reconciliation buffer fill — write into space that has already been read.

PayPal-specific tips

PayPal expects the backward-fill insight — that's the whole reason they like this problem. Forward-fill requires O(m) extra space; backward-fill is O(1). Bonus signal: relate it to in-place sort-merge in their daily settlement file processing.

Common mistakes

  • Filling forward — requires shifting nums1 right by n, which is O(m*n).
  • Forgetting to handle nums2 exhausted but not nums1 (already in correct position — no copy needed).
  • Off-by-one on the write pointer k = m + n - 1.

Follow-up questions

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

  • What if both arrays are large enough to overflow into one buffer?
  • What if you need to dedup at the same time?
  • Merge k sorted arrays in-place — feasible?

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

If you fill from the front, you can overwrite an unread element of nums1. Filling from the back guarantees the write pointer is always at or past the read pointer.

Why does the loop end when j < 0?

Remaining elements in nums1 (positions 0..i) are already in the right place. Remaining elements in nums2 must be copied. So we only need to keep going while j >= 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →