Mastering LeetCode Problem 0088

Created in May 04, 2026

2026   ·   Array   TwoPointers   Sorting   ·   LeetCode-Problems

Problem 0088: Merge Sorted Array

Array questions where everything is almost done for you — two sorted arrays, extra space already allocated — are exactly the kind of problems that interviewers use to test whether you can:

  • Respect in-place constraints
  • Use pointers intelligently
  • Avoid unnecessary extra memory

LeetCode 88 – Merge Sorted Array – is one of the most fundamental problems in this category.

In this post, we’ll cover:

  • The problem in plain English
  • Why a naïve merge can break the constraints
  • The key idea: merging from the back
  • A clean Python solution using three pointers
  • Step-by-step walkthrough with an example
  • Time & space complexity
  • Common pitfalls and interview tips

1. Problem Overview (In Plain English)

You are given:

  • A sorted array nums1 of length m + n
    • The first m elements are valid and sorted
    • The last n elements are just empty space (often filled with 0s)
  • A sorted array nums2 of length n
  • Two integers m and n, indicating how many meaningful elements each array contains

Your task:

Merge nums2 into nums1 as one sorted array, in-place.
Do not return a new array — modify nums1 directly.

After the function finishes:

  • nums1 should contain all m + n elements from both arrays, sorted.
  • The function should return None.

1.1. Example

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

Output:
nums1 = [1, 2, 2, 3, 5, 6]

The extra 0s in nums1 are just placeholders. After merging, nums1 becomes the fully sorted array of all 6 elements.

2. First Thoughts: The Wrong Way (But Very Tempting)

If there were no constraints, a very natural idea would be:

  1. Concatenate the two arrays: nums1_valid + nums2
  2. Sort the result
  3. Return a new array

Or in code:

merged = sorted(nums1[:m] + nums2)
return merged

But this breaks two important requirements of the problem:

  1. You must modify nums1 in-place
  2. You must not use extra space proportional to m + n

In interviews, ignoring these constraints is often treated as a wrong solution, even if the output is technically correct.

So we need a smarter strategy.

3. Key Insight: Merge From the Back

We’re merging two sorted arrays. This is similar to the merge step in Merge Sort:

  • Normally, we use two pointers from the front and build a result array.
  • But here, we cannot create a separate result array.

What makes this problem special:

  • nums1 already has enough space at the end to hold all elements (m + n).
  • The valid elements in nums1 are only in the first m positions.

If we try to merge from the front, we’ll end up overwriting values in nums1 that we haven’t processed yet. That leads to data loss and messy shifting.

So the trick is:

Use three pointers and merge from the end of nums1 backward.

3.1. Three Pointers

We define:

  • i = m - 1 → points to the last valid element in nums1
  • j = n - 1 → points to the last element in nums2
  • k = m + n - 1 → points to the last index of nums1 (where we will write)

At each step, we:

  1. Compare nums1[i] and nums2[j]
  2. Place the larger one at position k in nums1
  3. Move that pointer (i or j) to the left
  4. Move k to the left

We repeat this until we’ve placed all elements of nums2 into nums1.

Why this works:

  • We always write into the free space at the back.
  • We never overwrite any meaningful value in nums1 that we haven’t already used.
  • We maintain sorted order naturally because we always choose the largest remaining element.

4. Python Solution (In-Place, Three Pointers)

Here’s a clean and interview-ready implementation:

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int,
              nums2: List[int], n: int) -> None:
        """
        Merge nums2 into nums1 as one sorted array in-place.

        Args:
            nums1: List[int] of length m + n, where:
                   - First m elements are valid and sorted.
                   - Last n elements are placeholders (e.g. 0).
            m: Number of valid elements in nums1.
            nums2: List[int] of length n, sorted.
            n: Number of elements in nums2.

        Returns:
            None. The result is stored in nums1 in-place.
        """

        # Pointer i: last valid element in nums1
        i = m - 1
        # Pointer j: last element in nums2
        j = n - 1
        # Pointer k: last position in nums1 (full length)
        k = m + n - 1

        # Merge nums1 and nums2 starting from the end
        while j >= 0:
            # If there are still elements in nums1 to compare
            # and the current element in nums1 is larger,
            # place nums1[i] at nums1[k].
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                # Otherwise, place nums2[j] at nums1[k].
                nums1[k] = nums2[j]
                j -= 1

            k -= 1

        # No return needed; nums1 is modified in-place.

This is essentially your solution, Mohammad Hossein, with:

  • The correct method signature (self included)
  • No print inside the function
  • Clear comments and docstring

5. Walkthrough: Step-by-Step Example

Let’s walk through the main example to really lock in the intuition.

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

Initial pointers:

  • i = m - 1 = 2 → nums1[i] = 3
  • j = n - 1 = 2 → nums2[j] = 6
  • k = m + n - 1 = 5 → nums1[k] (where we’ll write)

5.1. Iteration 1

  • Compare nums1[i] = 3 and nums2[j] = 6
  • 6 is larger → place it at nums1[k] 
nums1[k] = nums2[j]  → nums1[5] = 6

nums1 = [1, 2, 3, 0, 0, 6]
j = 1
k = 4

5.2. Iteration 2

  • nums1[i] = 3, nums2[j] = 5
  • 5 is larger → place it at nums1[4] 
nums1[4] = 5

nums1 = [1, 2, 3, 0, 5, 6]
j = 0
k = 3

5.3. Iteration 3

  • nums1[i] = 3, nums2[j] = 2
  • 3 is larger → place it at nums1[3] 
nums1[3] = 3

nums1 = [1, 2, 3, 3, 5, 6]
i = 1
k = 2

5.4. Iteration 4

  • nums1[i] = 2, nums2[j] = 2
  • They are equal; we can choose nums2[j] (or nums1[i], both fine)
nums1[2] = nums2[0] = 2

nums1 = [1, 2, 2, 3, 5, 6]
j = -1
k = 1

Loop condition: while j >= 0 → now j = -1, so we stop.

At this point:

  • All elements of nums2 have been merged into nums1.
  • Any remaining elements on the left side of nums1 (indexes 0..i) are already in the correct place.

Final result:

nums1 = [1, 2, 2, 3, 5, 6]

Exactly what we want.

6. Edge Cases to Consider

6.1. nums2 is empty (n = 0)

nums1 = [1, 2, 3]
m = 3
nums2 = []
n = 0
  • The loop while j >= 0 never runs.
  • nums1 stays as [1, 2, 3] → already correct.

6.2. nums1 has no valid elements initially (m = 0)

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

Initial pointers:

  • i = m - 1 = -1
  • j = 2
  • k = 2

Since i < 0, the condition i >= 0 and nums1[i] > nums2[j] is false,
so we always take elements from nums2:

  • nums1[2] = 6
  • nums1[1] = 5
  • nums1[0] = 2

Final nums1 = [2, 5, 6].

6.3. All elements in nums2 are smaller

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

You’ll end up filling nums1 from the back with [6, 5, 4, 3, 2, 1] in reverse,
but because we’re going from the end and comparing correctly, the final array will still be [1, 2, 3, 4, 5, 6].

7. Time and Space Complexity

7.1. Time Complexity

We process each element at most once:

  • Each iteration moves k one step to the left.
  • Each iteration also moves either i or j.

So the total number of iterations is at most m + n.

$\text{Time Complexity} = O(m + n)$

7.2. Space Complexity

We only use a few extra integer variables (i, j, k):

  • No extra arrays
  • No additional data structures

$\text{Space Complexity} = O(1)$

This fully satisfies the in-place constraint.

8. Common Pitfalls in Interviews

8.1. Forgetting the In-Place Requirement

A very common wrong answer is:

result = sorted(nums1[:m] + nums2)
return result

Even if it “works” in a normal environment, it fails this LeetCode problem and typically gets rejected in interviews because:

  • It uses extra O(m + n) space.
  • It does not modify nums1 in-place.

8.2. Merging from the Front and Shifting

Some candidates try to insert elements from nums2 into the front of nums1 and shift elements to the right one by one.

This leads to:

  • Complicated code
  • Potential bugs with indices
  • Often O(n^2) time in the worst case

The three-pointer backward merge is cleaner and optimal.

8.3. Off-by-One Errors with Indices

Pay attention to:

  • i = m - 1
  • j = n - 1
  • k = m + n - 1

Using m, n, or m + n directly as indices is a typical source of bugs.

8.4. Returning the Array

This function is void in many languages (e.g., void in C++/Java, None in Python).
The correct behavior is:

  • Modify nums1 in-place
  • Do not return anything

On LeetCode, the platform checks the content of nums1 after the function runs.

9. Interview Takeaways

LeetCode 88 is more than just “merge two arrays”:

  • It’s a textbook example of:
    • In-place operations
    • Two/three-pointer techniques
    • Respecting time and space constraints
  • It trains you to:
    • Think from the end instead of always from the beginning
    • Exploit the structure of the input (sorted arrays + extra space)

Once you master this pattern, it will help you in many similar problems:

  • Merging sorted lists
  • Merging intervals
  • Implementing merge sort manually
  • Problems that combine “sorted + extra space at the end”