Skip to main content

8. Merge Sorted Array

easyAsked at ServiceNow

Merge nums2 into nums1 (which has trailing zero slots) so that nums1 stays sorted, in place. ServiceNow uses this to test the back-to-front three-pointer trick — the same shape they apply when blending two priority queues without an auxiliary buffer.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2026-Q1)— ServiceNow loops use this to probe in-place mutation discipline.
  • Blind (2025-09)— Cited as a recurring SDE-I screen question at ServiceNow.

Problem

You are given two sorted integer arrays nums1 and nums2, and two integers m and n representing the number of elements in each. Merge nums2 into nums1 as one sorted array. nums1 has length m + n; the first m positions are the initial elements and the last n positions are zeros that 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]

Example 3

Input
nums1 = [0], m = 0, nums2 = [1], n = 1
Output
[1]

Approaches

1. Copy and sort

Copy nums2 into the back slots of nums1, then sort the whole thing.

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 inputs are already sorted. ServiceNow grades this as missing the point.

2. Back-to-front three-pointer merge

Place the larger of nums1[i] and nums2[j] at the back. Walk i, j down from the end. This avoids overwriting unread nums1 entries.

Time
O(m + n)
Space
O(1)
function merge(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, write = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[write--] = nums1[i--];
    } else {
      nums1[write--] = nums2[j--];
    }
  }
}

Tradeoff: Linear time, no extra space. Walking from the back is the trick — front-to-back would clobber unread nums1 entries.

ServiceNow-specific tips

ServiceNow grades for the back-to-front insight — they want you to recognize the trailing zeros as scratch space and walk pointers downward. Bonus signal: note that the loop only needs to continue while j >= 0; if nums2 is exhausted first, nums1's prefix is already in place.

Common mistakes

  • Walking front-to-back and clobbering nums1 entries you haven't read yet.
  • Looping until both i and j are negative — extra work; you only need j >= 0.
  • Forgetting to handle the case where m = 0 (everything comes from nums2).

Follow-up questions

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

  • Merge k sorted arrays in place — heap-based extension.
  • Merge two sorted linked lists (LC 21).
  • Median of two sorted arrays (LC 4) — same pair of inputs, harder query.

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

Front-to-back, the write pointer would overlap with unread nums1 entries. Back-to-front, the write pointer always lives in the zero slots until nums1's prefix is consumed.

What if nums1 is fully consumed first?

Then i goes negative and the condition `i >= 0 && nums1[i] > nums2[j]` short-circuits to false, so we copy from nums2 until j goes negative.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →