#88

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Merge Sorted Array

Merge two sorted arrays into the first array in non-decreasing order, using a two-pointer approach.

Problem Statement

You are given two integer arrays, nums1 and nums2, both sorted in non-decreasing order, and two integers m and n representing the number of valid elements in nums1 and nums2, respectively. The task is to merge the elements of nums2 into nums1, ensuring the merged result is sorted in non-decreasing order. The length of nums1 is m + n, where the first m elements are filled with valid values, and the last n elements are zeros, providing space for the elements of nums2.

The final merged array must be stored inside nums1. There is no need to return the array as the result is updated directly in nums1. The merging should happen in-place, and you must avoid using extra space to store the merged array.

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]

The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2

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

Output: [1]

The arrays we are merging are [1] and []. The result of the merge is [1].

Example 3

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

Output: [1]

The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

Solution Approach

Two-Pointer Approach

We can solve this problem using the two-pointer technique by starting from the end of the nums1 array. Since nums1 already has enough space, we can place elements from the back of nums1, comparing the largest unprocessed elements from both arrays. At each step, the larger element is moved to its correct position in nums1, and the corresponding pointer is decremented.

Handling Zeros in nums1

The zeros in nums1 act as placeholders for the elements of nums2. We avoid overwriting existing values in nums1 by starting the merging process from the back of the array, ensuring that we move elements only when necessary. This allows us to work within the given constraints and guarantees the space is used optimally.

Edge Case Considerations

We need to handle edge cases such as when nums2 is empty (n=0) or when nums1 has no valid elements (m=0). For these cases, we can directly copy nums2 into nums1 if nums1 is empty, or do nothing if nums2 is empty. Additionally, we need to make sure that all elements are properly placed, even if one array is exhausted before the other.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(m + n), where m and n are the lengths of nums1 and nums2, as we traverse both arrays once. The space complexity is O(1) since the merging happens in-place without extra space requirements, aside from the input arrays themselves.

What Interviewers Usually Probe

Do you understand how to efficiently merge arrays in-place?
Can you explain why the two-pointer technique is optimal for this problem?
Will you consider edge cases like when one of the arrays is empty?

Common Pitfalls or Variants

Common pitfalls

Overwriting elements in nums1 before reaching the end, which can lead to data loss.
Forgetting to handle the case when nums2 is empty, which should result in no changes to nums1.
Assuming that elements of nums1 after m are zero and should be directly ignored, without considering the potential for overflow or incorrect indexing.

Follow-up variants

Merge k sorted arrays using a similar two-pointer technique.
Merge two sorted linked lists in place.
Merge two arrays without extra space, considering the possibility of unequal sizes.

FAQ

How does the two-pointer approach solve the 'Merge Sorted Array' problem?

The two-pointer approach starts at the end of both arrays, comparing and placing the largest elements in the right positions within nums1, ensuring an in-place merge.

What should be done when nums2 is empty?

If nums2 is empty, no elements need to be merged, and nums1 remains unchanged, as its first m elements are already sorted.

Why is the space complexity O(1) in this problem?

Since we are merging the arrays in-place within nums1 without using extra arrays, the space complexity remains O(1).

How do you handle the zeros in nums1 when merging?

The zeros act as placeholders. By merging from the back of nums1, we can avoid overwriting valid elements while filling nums1 with merged values.

What are common edge cases for the 'Merge Sorted Array' problem?

Edge cases include when nums2 is empty, nums1 is initially empty, or when the arrays are already sorted. These scenarios need special handling for efficiency.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ pointing to the end of two arrays, and a pointer $k$ pointing to the end of the merged array.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        k = m + n - 1
        i, j = m - 1, 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

Continue Practicing

#75 sort colors #18 4sum #16 3sum closest