Skip to main content

9. Merge Sorted Array

easyAsked at Workday

Merge two sorted arrays in-place into the first one (sized for both). Workday uses this for end-to-front pointer practice — merging current-period and adjustment ledger entries when only the result buffer exists.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE1 screen.
  • LeetCode Discuss (2026)— Workday onsite phone — common warmup.

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 merged array is stored inside nums1, which has length m + n (the last n slots are 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. Copy + sort

Copy nums2 into nums1's tail, then sort.

Time
O((m+n) log (m+n))
Space
O(1)
for (let i = 0; i < n; i++) nums1[m + i] = nums2[i];
nums1.sort((a,b)=>a-b);

Tradeoff: Throws away the sorted property of both inputs. Don't.

2. Three-pointer from the back

Place the larger of nums1[i] and nums2[j] at nums1[k], working backward. No overwrites because we fill empty tail first.

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 (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k--] = nums1[i--];
    } else {
      nums1[k--] = nums2[j--];
    }
  }
  while (j >= 0) nums1[k--] = nums2[j--];
  // Remaining nums1 prefix is already in place.
}

Tradeoff: Back-to-front means we never overwrite unprocessed data. The 'remaining nums1' loop is unnecessary — those elements are already in their final position.

Workday-specific tips

Workday grades on whether you spot that filling from the BACK avoids overwrites. Front-to-back forces you to shift; back-to-front is the elegant invariant. Articulate this insight before coding.

Common mistakes

  • Filling front-to-back — overwrites unprocessed nums1 data, forces a temp buffer.
  • Forgetting the 'leftover nums2' loop when m runs out.
  • Writing a 'leftover nums1' loop — unnecessary, those are already in place.

Follow-up questions

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

  • Merge K Sorted Arrays (LC 23 list variant).
  • What if the buffer wasn't pre-allocated?
  • Find Median from Two Sorted Arrays (LC 4).

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 front-to-back, you overwrite unprocessed nums1 elements. Back-to-front uses the empty tail as scratch space until both inputs are consumed.

Why no leftover-nums1 loop?

If j hits -1 first, the remaining nums1[0..i] is already at indices [0..i] of nums1 — no work needed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →