LeetCode Problem 88

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Sorting

Solution

LeetCode 88 - Merge Sorted Array

Problem Understanding

This problem gives us two arrays, nums1 and nums2, where both arrays are already sorted in non-decreasing order. We are also given two integers, m and n, which tell us how many valid elements exist in each array.

The important detail is that nums1 has extra space at the end. Its total size is m + n, where only the first m elements are meaningful data. The remaining n positions are placeholders, initialized to 0, and are reserved so that the merged result can fit inside nums1.

The goal is to merge all elements from nums2 into nums1, producing one fully sorted array in-place. The function should not return anything. Instead, it must directly modify nums1.

For example:

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

The meaningful elements are:

• nums1 -> [1,2,3]
• nums2 -> [2,5,6]

After merging and sorting, nums1 should become:

• [1,2,2,3,5,6]

The constraints are relatively small, since m + n <= 200, so even less efficient solutions would technically work within time limits. However, the follow-up specifically asks for an O(m + n) solution, which strongly suggests using a two-pointer merge strategy similar to the merge step of merge sort.

Several edge cases are important:

• nums2 may be empty
• nums1 may initially contain no valid elements
• All elements in one array may be smaller or larger than all elements in the other
• Duplicate values may appear
• Negative numbers are allowed

A naive in-place merge from the front can accidentally overwrite unprocessed values in nums1, so careful handling is required.

Approaches

Brute Force Approach

A straightforward solution is to copy all elements from nums2 into the empty portion of nums1, then sort the entire array.

The algorithm works like this:

1. Insert every element from nums2 into the unused positions at the end of nums1
2. Sort the entire nums1 array

This approach is correct because after combining all elements into one array, sorting restores the required non-decreasing order.

However, this solution is not optimal. Sorting takes O((m+n) log(m+n)) time, which is slower than necessary because the arrays are already individually sorted.

Optimal Approach

The key insight is that both arrays are already sorted. This means we can merge them similarly to the merge step in merge sort.

The challenge is performing the merge in-place without overwriting values in nums1 that we still need to process.

The important observation is that the empty space already exists at the end of nums1. Instead of merging from the beginning, we can merge from the back.

We use three pointers:

• One pointer at the last valid element of nums1
• One pointer at the last element of nums2
• One pointer at the final position in nums1

At each step, we place the larger value into the back position and move the corresponding pointer backward.

Because we fill the array from right to left, we never overwrite unprocessed data.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m+n) log(m+n))	O(1) or O(log(m+n)) depending on sort	Copy nums2 into nums1, then sort
Optimal	O(m+n)	O(1)	Merge from the back using three pointers

Algorithm Walkthrough

Optimal Two-Pointer Algorithm

1. Initialize three pointers.

The first pointer, i, starts at m - 1, which is the last valid element in nums1.

The second pointer, j, starts at n - 1, which is the last element in nums2.

The third pointer, write_index, starts at m + n - 1, which is the final position in nums1. 2. Compare the elements pointed to by i and j.

Since both arrays are sorted, the larger of these two values must belong at the end of the merged array. 3. Place the larger value at nums1[write_index].

If nums1[i] > nums2[j], place nums1[i] into the write position and move i backward.

Otherwise, place nums2[j] into the write position and move j backward. 4. Move write_index backward.

After placing one element, decrement write_index because the next largest value belongs one position earlier. 5. Continue until all elements from nums2 are processed.

The loop condition is usually while j >= 0.

If elements remain in nums1, they are already in the correct position, so no additional work is needed. 6. Stop when j < 0.

At this point, every element from nums2 has been merged correctly into nums1.

Why it works

The algorithm maintains the invariant that everything to the right of write_index is already correctly placed in sorted order.

At every step, we choose the largest remaining element from either array and place it into the current back position. Since we fill positions from right to left, no unprocessed value in nums1 gets overwritten.

Because each element is processed exactly once, the final array is fully sorted and complete.

Python Solution

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        
        i = m - 1
        j = n - 1
        write_index = m + n - 1

        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[write_index] = nums1[i]
                i -= 1
            else:
                nums1[write_index] = nums2[j]
                j -= 1

            write_index -= 1

The implementation follows the exact algorithm described above.

The variable i tracks the current element in the valid portion of nums1. The variable j tracks the current element in nums2. The variable write_index tracks where the next largest element should be written.

The condition i >= 0 is important because once all valid elements from nums1 are exhausted, we must continue copying the remaining elements from nums2.

The loop continues while j >= 0 because every element from nums2 must eventually be placed into nums1. If elements remain in the original part of nums1, they are already correctly positioned.

This implementation modifies nums1 directly and uses only constant extra memory.

Go Solution

func merge(nums1 []int, m int, nums2 []int, n int) {
    i := m - 1
    j := n - 1
    writeIndex := m + n - 1

    for j >= 0 {
        if i >= 0 && nums1[i] > nums2[j] {
            nums1[writeIndex] = nums1[i]
            i--
        } else {
            nums1[writeIndex] = nums2[j]
            j--
        }

        writeIndex--
    }
}

The Go implementation is nearly identical to the Python version.

Go slices behave similarly to dynamic arrays, so modifying nums1 inside the function directly changes the original slice contents.

There are no integer overflow concerns here because the indices are very small and well within Go's integer range.

Go does not distinguish between empty and nil slices in a way that affects this algorithm. As long as the provided constraints are satisfied, the implementation works correctly.

Worked Examples

Example 1

Input:

nums1 = [1,2,3,0,0,0]
m = 3

nums2 = [2,5,6]
n = 3

Initial pointers:

• i = 2 → value 3
• j = 2 → value 6
• write_index = 5

Step	nums1	i	j	write_index	Action
Initial	[1,2,3,0,0,0]	2	2	5	Start
1	[1,2,3,0,0,6]	2	1	4	Place 6
2	[1,2,3,0,5,6]	2	0	3	Place 5
3	[1,2,3,3,5,6]	1	0	2	Place 3
4	[1,2,2,3,5,6]	1	-1	1	Place 2

Final result:

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

Example 2

Input:

nums1 = [1]
m = 1

nums2 = []
n = 0

Initial pointers:

• i = 0
• j = -1

Since j < 0, the loop never executes.

Final result:

[1]

Example 3

Input:

nums1 = [0]
m = 0

nums2 = [1]
n = 1

Initial pointers:

• i = -1
• j = 0
• write_index = 0

Step	nums1	i	j	write_index	Action
Initial	[0]	-1	0	0	Start
1	[1]	-1	-1	-1	Place 1

Final result:

[1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m+n)	Each element is processed at most once
Space	O(1)	Only a few pointer variables are used

The algorithm is linear because every element from both arrays is examined and placed exactly one time. No nested loops or repeated scanning occur.

The space complexity is constant because the merge is performed directly inside nums1 without allocating another array proportional to the input size.

Test Cases

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1
        j = n - 1
        write_index = m + n - 1

        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[write_index] = nums1[i]
                i -= 1
            else:
                nums1[write_index] = nums2[j]
                j -= 1

            write_index -= 1

solution = Solution()

# Example 1
nums1 = [1,2,3,0,0,0]
solution.merge(nums1, 3, [2,5,6], 3)
assert nums1 == [1,2,2,3,5,6]  # standard merge case

# Example 2
nums1 = [1]
solution.merge(nums1, 1, [], 0)
assert nums1 == [1]  # nums2 empty

# Example 3
nums1 = [0]
solution.merge(nums1, 0, [1], 1)
assert nums1 == [1]  # nums1 initially empty

# All nums2 elements smaller
nums1 = [4,5,6,0,0,0]
solution.merge(nums1, 3, [1,2,3], 3)
assert nums1 == [1,2,3,4,5,6]  # requires shifting everything

# All nums2 elements larger
nums1 = [1,2,3,0,0,0]
solution.merge(nums1, 3, [4,5,6], 3)
assert nums1 == [1,2,3,4,5,6]  # nums2 appended at end

# Duplicate values
nums1 = [1,2,2,0,0,0]
solution.merge(nums1, 3, [2,2,3], 3)
assert nums1 == [1,2,2,2,2,3]  # handles duplicates correctly

# Negative numbers
nums1 = [-5,-3,-1,0,0,0]
solution.merge(nums1, 3, [-4,-2,0], 3)
assert nums1 == [-5,-4,-3,-2,-1,0]  # negative values

# Single element arrays
nums1 = [2,0]
solution.merge(nums1, 1, [1], 1)
assert nums1 == [1,2]  # minimal non-trivial case

# Both arrays contain zeros as valid values
nums1 = [0,0,3,0,0,0]
solution.merge(nums1, 3, [0,0,1], 3)
assert nums1 == [0,0,0,0,1,3]  # valid zeros in arrays

Test	Why
[1,2,3] + [2,5,6]	Standard merge scenario
nums2 = []	Ensures empty second array works
m = 0	Ensures empty first array works
All nums2 elements smaller	Verifies shifting behavior
All nums2 elements larger	Verifies simple append behavior
Duplicate values	Confirms duplicates handled correctly
Negative numbers	Ensures ordering with negatives
Single element arrays	Tests smallest non-trivial input
Arrays containing valid zeros	Distinguishes placeholders from actual values

Edge Cases

nums2 Is Empty

When n = 0, there is nothing to merge. This case can easily cause bugs if the algorithm assumes both arrays contain elements.

The implementation handles this naturally because j starts at -1. The loop condition while j >= 0 immediately fails, so nums1 remains unchanged.

nums1 Has No Valid Elements

When m = 0, all actual data comes from nums2. A buggy implementation may incorrectly compare against placeholder zeros in nums1.

This solution avoids that issue because i starts at -1. The condition i >= 0 fails, so the algorithm copies all elements directly from nums2 into nums1.

All Elements in nums2 Are Smaller

Consider:

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

A forward merge can overwrite values in nums1 before they are processed.

The backward merge strategy prevents this problem entirely. The algorithm fills positions from the end, preserving all unprocessed values until they are no longer needed.

Duplicate Values

Arrays may contain repeated values such as:

nums1 = [1,2,2]
nums2 = [2,2,3]

Some incorrect implementations accidentally skip duplicates or mishandle pointer movement.

This algorithm compares values independently at every step and copies exactly one element each iteration, ensuring all duplicates appear correctly in the final merged array.