NUHMAN.com

Introduction

LeetCode 88: Merge Sorted Array is a classic problem that tests your ability to merge two sorted arrays into a single sorted array. However, this problem presents an additional constraint: you must do it in-place, modifying the first array to hold the merged result.

This problem can be efficiently solved using a two-pointer technique that leverages the fact that both input arrays are already sorted.

Problem Statement

You are given two sorted integer arrays nums1 and nums2, where:

• nums1 has a length of m + n, with the first m elements being the elements to be merged and the remaining n elements initialized to 0.
• nums2 has a length of n.

You need to merge the two arrays into a single sorted array in non-decreasing order. The merge should be done in-place within nums1.

Example:

go

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

Approach: Two Pointers (Optimized In-place)

Idea:

To merge the two sorted arrays in-place, we can take advantage of the fact that both arrays are sorted. The idea is to start from the end of both arrays and compare the elements. We can place the larger element at the last position of nums1 and reduce the size of the arrays as we go.

Steps:

1. Start with two pointers: one at the end of the valid part of nums1 (at index m-1), and one at the end of nums2 (at index n-1).
2. Start filling nums1 from the back, comparing the elements from nums1 and nums2. Place the larger element at the end of nums1.
3. Once all elements from nums2 have been merged into nums1, if any elements are left in nums1, they are already in the correct position.
4. This ensures an O(n + m) time complexity with an O(1) space complexity.

Go Implementation

go

func merge(nums1 []int, m int, nums2 []int, n int) {
    // Start from the end of both arrays
    i, j, k := m-1, n-1, m+n-1

    // Merge the arrays in reverse order
    for i >= 0 && j >= 0 {
        if nums1[i] > nums2[j] {
            nums1[k] = nums1[i]
            i--
        } else {
            nums1[k] = nums2[j]
            j--
        }
        k--
    }

    // If there are remaining elements in nums2, copy them over
    for j >= 0 {
        nums1[k] = nums2[j]
        j--
        k--
    }
}

Explanation

1. Pointers (i, j, k):

• i points to the last valid element in nums1.
• j points to the last element in nums2.
• k points to the last position in nums1 (the total length of nums1 after merging).

1. Merging Loop:
2. We compare the elements of nums1[i] and nums2[j]. The larger element is placed at nums1[k], and the corresponding pointer (i or j) is decremented. After placing the element, we also decrement k to move to the next position.
3. Copying Remaining Elements:
4. After the main loop, if there are any elements left in nums2, we copy them into nums1. Since nums1's remaining elements are already in place, there's no need to handle them.
5. Space and Time Complexity:
6. The solution works in-place, with a time complexity of O(m + n), where m is the number of valid elements in nums1 and n is the number of elements in nums2. The space complexity is O(1), as we do not use any additional data structures.

Time and Space Complexity

MetricComplexityTime ComplexityO(m + n)Space ComplexityO(1)

Where m is the number of elements in the original nums1 (before the 0's) and n is the number of elements in nums2.

Edge Cases

1. Empty nums2: If nums2 is empty, nums1 remains unchanged.

• Example: nums1 = [1, 2, 3], nums2 = []
• Output: [1, 2, 3]

1. Empty nums1: If nums1 has no valid elements, we just copy all elements from nums2 into nums1.

• Example: nums1 = [0, 0, 0], nums2 = [1, 2, 3]
• Output: [1, 2, 3]

1. nums1 has larger elements than nums2: The merged result will have nums1 elements in their original order before the nums2 elements.

• Example: nums1 = [5, 6, 7, 0, 0, 0], nums2 = [1, 2, 3]
• Output: [1, 2, 3, 5, 6, 7]

1. All elements of nums2 are larger than nums1: All nums2 elements will be placed before nums1's elements in the merged result.

• Example: nums1 = [1, 2, 3], nums2 = [4, 5, 6]
• Output: [1, 2, 3, 4, 5, 6]

Conclusion

LeetCode 88 is a fundamental problem in array manipulation that can be solved using the two-pointer technique. By starting from the end of the arrays, we can merge the sorted arrays efficiently in-place, maintaining O(m + n) time complexity and O(1) space complexity.

This problem is a great exercise for learning efficient merging techniques, especially when dealing with constraints that require in-place modifications.