Skip to main content

9. Merge Sorted Array

easyAsked at Palantir

Merge two sorted arrays in-place where the first has extra space at the end. Palantir asks this to test the right-to-left two-pointer trick, which prevents overwriting unread data — a pattern they use in in-place ETL compaction.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2025-12)— Palantir FDE phone screen, asked alongside merge-k-lists.
  • Blind (2026-Q1)— Common Palantir warm-up; bonus signal is right-to-left fill.

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

Copy nums2 into nums1's tail and sort the whole thing.

Time
O((m+n) log(m+n))
Space
O(1) (in-place sort)
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. Reject.

2. Two-pointer right-to-left

Walk from the back of both arrays. Place the LARGER value at nums1[m+n-1] and decrement. This avoids overwriting unread data in nums1.

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, O(1) space. The right-to-left direction is the key insight; left-to-right would overwrite unread nums1 entries.

Palantir-specific tips

Palantir grades this on whether you choose right-to-left immediately. If you start left-to-right and pivot when you spot the overwrite issue, that's still a pass — but starting right-to-left is the bonus signal. The loop condition while (j >= 0) is cleaner than while (i >= 0 || j >= 0) because once nums2 is exhausted, the rest of nums1 is already in place.

Common mistakes

  • Going left-to-right and overwriting nums1's unread elements.
  • Using while (i >= 0 || j >= 0) — more code, since you also need to handle the i >= 0 && j < 0 case explicitly.
  • Forgetting that nums1 is already partially filled — copying nums2 to the front overwrites real data.

Follow-up questions

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

  • Merge k sorted arrays where the first has space for all (LC 23 variant).
  • What if nums1 doesn't have extra space? (Allocate output, two-pointer left-to-right.)
  • Merge while de-duplicating exact matches.

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 right-to-left?

Left-to-right would overwrite nums1's still-unread elements. Right-to-left writes into the trailing zeros, which we know are unused.

Why is the loop condition just while (j >= 0)?

When j < 0, all of nums2 is placed and the remaining nums1 prefix is already sorted in place. No further work.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →