algoadvance

Problem Statement

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 nums2 into nums1 such that the merged array is also sorted in non-decreasing order.

Clarifying Questions

1. What do you mean by merging nums2 into nums1?
   • Typically, nums1 will have enough space allocated at the end to hold all elements of nums2.
2. Are the inputs guaranteed to be sorted?
   • Yes, both nums1 and nums2 are sorted in non-decreasing order.
3. Can we assume that nums1 has enough space to hold the combined elements of both arrays?
   • Yes, nums1 has a size of m + n where the last n elements are empty (0) and can be used to merge nums2.

Strategy

To merge nums2 into nums1, we can take a backwards approach. Because both arrays are sorted, we start comparing elements from the end of both arrays and place the larger element at the end of nums1. This ensures we don’t overwrite any elements in nums1 that we haven’t processed yet:

1. Initialize three pointers:
   • p1 pointing to the last element of the first m elements in nums1
   • p2 pointing to the last element in nums2
   • p pointing to the last position of nums1
2. Iterate in reverse order:
   • Compare nums1[p1] and nums2[p2]
   • Place the larger value at nums1[p]
   • Move pointer p backward
   • Move the corresponding pointer (p1 or p2) backward
3. If any elements are left in nums2 (i.e., p2 >= 0), copy them into nums1.

Code

Here is the Python implementation of the strategy described:

def merge(nums1, m, nums2, n):
    # Start from the last positions of nums1 and nums2 respectively
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    # Merge in reverse order
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # If there are remaining elements in nums2, copy them
    # This caters for cases where all elements in nums1 are already in correct position
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p -= 1
        p2 -= 1

Time Complexity

• Time Complexity: O(m + n) because we iterate through each element of nums1 and nums2 exactly once.
• Space Complexity: O(1) because we do not use any additional space proportional to the input size. We are modifying nums1 in place.

This method solves the problem efficiently and adheres to the constraints provided.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?