Skip to main content

8. Merge Sorted Array

easyAsked at Salesforce

Merge two sorted arrays in-place into the first array, which has trailing zeros for the second's contents. Salesforce uses this to test the reverse-merge trick essential for any in-place sorted data manipulation.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Common on Salesforce backend phone screens for the reverse-merge insight.
  • Blind (2025-10)— Used as a building-block warmup before k-way merge questions.

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 but stored inside nums1. nums1 has length 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. Copy nums2 and sort

Copy nums2 into the trailing zeros, then sort the whole array.

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: Throws away the sorted invariant. Salesforce will push you to O(m+n).

2. Reverse three-pointer merge

Walk from the END of both arrays. Write the larger of nums1[i] and nums2[j] to nums1[k], decrementing all three. This avoids overwriting unread nums1 values.

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 reverse direction is the key insight — writing from the front would clobber unread values in nums1. Loop only needs to run until j < 0 (nums1 leftover is already in place).

Salesforce-specific tips

Salesforce specifically grades on whether you spot the 'merge from the end' trick. Candidates who try to merge from the front and panic when they realize they're overwriting unread values lose points. Bonus signal: explain WHY reverse merge works (the trailing zeros give you scratch space exactly where you need it).

Common mistakes

  • Merging from the front and overwriting nums1's unread values.
  • Looping while i >= 0 && j >= 0 — stops too early when nums2 has values smaller than nums1's smallest.
  • Forgetting that nums1's leftover doesn't need to be moved — it's already in the right place.

Follow-up questions

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

  • Merge k sorted arrays in place.
  • Merge two sorted lists (LC 21 — linked list version).
  • What if nums1 didn't have trailing zeros — could you still merge in O(m+n)?

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 merge from the end?

The trailing zeros give you free scratch space at the end. Writing from the front would require shifting elements right, turning O(m+n) into O(m*n).

Why does the loop only check j >= 0?

If nums2 is exhausted, nums1's remaining values are already correctly positioned at the front. No more work needed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →