Question

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

The Efficient Approach

To solve this problem efficiently, we utilize a technique that involves iterating from the end of the arrays rather than the beginning. This is a strategic move as it allows us to fill nums1 from the end, avoiding the overwriting of elements that we have not yet processed.

The Solution: Step-by-Step

Here is a JavaScript function that elegantly solves this problem:

javascriptCopy code

def merge(nums1, m, nums2, n):
    i = m - 1  # Pointer for the last element in the original part of nums1
    j = n - 1  # Pointer for the last element in nums2
    k = m + n - 1  # Pointer for the last position in nums1

    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]  # Place the larger element at the end of nums1
            k -= 1
            i -= 1
        else:
            nums1[k] = nums2[j]  # Place the element from nums2 in nums1
            k -= 1
            j -= 1

How Does This Work?

Initialization: We start by initializing three pointers:

  • i points to the last element of the original nums1.
  • j points to the last element of nums2.
  • k is set to the last position of the nums1 array.

Merging: The while loop continues as long as there are elements in nums2 (i.e., j >= 0). Inside the loop, we compare the elements pointed to by i and j.

  • If nums1[i] is greater than nums2[j], we place nums1[i] in the position pointed to by k in nums1, and decrement both i and k.
  • Otherwise, we place nums2[j] in the position pointed to by k, and decrement both j and k.
  1. No Need to Handle Remaining nums1 Elements: Since we are filling nums1 from the end, if there are any elements left in the original nums1 array, they are already in their correct position.
  2. In-Place Operation: The entire operation is done within the nums1 array, ensuring that the space complexity remains constant, i.e., O(1).

Complexity Analysis

  • Time Complexity: O(m+n) - Each element in both nums1 and nums2 is looked at a maximum of once.
  • Space Complexity: O(1) - No extra space is used; all operations are performed in-place.

Conclusion

This solution to LeetCode 88 demonstrates a clever use of pointers and in-place array manipulation. It's an efficient and elegant approach that handles the merging with a minimal time and space complexity, showcasing the power of algorithmic thinking in solving coding problems.

Checkout more Leetcode solutions.