Merge Sorted Array — Three Pointers from the End at Microsoft and Bloomberg

Problem Statement#

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order, with sizes m and n. Merge nums2 into nums1 as one sorted array. The final array is stored inside nums1, which has length m + n, where the last n slots are zero placeholders.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

Input:  nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: nums1 = [1,2,2,3,5,6]

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

Why This Problem Matters#

LeetCode 88 Merge Sorted Array is the most asked merge problem at Microsoft and Bloomberg. It directly tests whether candidates understand that merging from the front would overwrite unread data in nums1, so the merge must happen from the back where the empty slots already are.

Amazon uses this problem to gauge whether a candidate can correctly handle the case where one array is exhausted before the other. Apple has been seen pairing this with a sorted linked list merge as a one-two question in onsite rounds.

The technique generalizes to LC 977 Squares of a Sorted Array, LC 21 Merge Two Sorted Lists, and the merge step of merge sort itself.

The Core Insight#

Merging from the front into nums1 would overwrite elements of nums1 that have not been compared yet. Merging from the back avoids that hazard because the back of nums1 is empty.

Use three pointers: i = m - 1 for the last real element of nums1, j = n - 1 for the last element of nums2, and k = m + n - 1 for the write position. At each step, place the larger of nums1[i] and nums2[j] at nums1[k] and decrement the appropriate pointer.

When j reaches -1, the remaining elements of nums1 are already in place. When i reaches -1, copy any remaining elements of nums2 into the front of nums1.

Visual Dry Run#

For nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3:

Solution (Optimal)#

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

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

Time: O(m + n) — single pass over both arrays Space: O(1) — three indices, no auxiliary buffer

Common Mistakes#

• Merging from the front, which overwrites unread nums1 elements
• Forgetting that nums1 already has trailing zeros and using nums1.append
• Stopping the loop when i < 0 and forgetting to drain remaining nums2 elements
• Allocating a new array, which violates the in-place constraint even though it works
• Confusing m and nums1.length; the problem uses m + n == nums1.length

Interview Tips#

• Lead with the merge-from-front pitfall: "If we merge from the front we would overwrite unread data, so we go from the back where the empty slots are"
• Walk through both an interleaved example and a fully-disjoint example to show pointer drainage
• Mention the structural similarity to LC 977 Squares of a Sorted Array
• Note that the loop only needs to continue while j >= 0, since leftover nums1 elements are already in place

Follow-up Questions#

• What if you cannot modify nums1 and must return a new array? (Hint: standard merge step, O(m + n) space)
• How would you merge k sorted arrays? (Hint: LC 23, min heap)
• What if the arrays are sorted in non-increasing order? (Hint: same logic, reverse pointer directions)
• How would you merge two sorted linked lists? (Hint: LC 21, dummy head and pointer splicing)
• How would you handle duplicates with a uniqueness constraint? (Hint: combine with LC 26 deduplication template)

Key Takeaways#

• LeetCode 88 Merge Sorted Array uses three pointers walking from the back of both arrays
• Merging from the back avoids overwriting unread elements in nums1
• O(m + n) time and O(1) space are required by the in-place constraint
• The loop only needs j >= 0 because leftover nums1 elements are already in their final positions
• The technique generalizes to LC 977, LC 21, and the merge step of merge sort
• Microsoft, Bloomberg, and Amazon use this as a 10 minute interview opener
• Allocating a new array is a common rejection trigger even though the answer is correct