Problem Statement in English

You’re 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 in place so that nums1 remains sorted in non-decreasing order.

Perform the merge in-place.

Approach

The key idea is to start merging from the end of both arrays, which allows us to avoid overwriting elements in nums1 that haven’t been processed yet.

We maintain 3 pointers — one for the end of nums1, one for the end of nums2, and one for the position where we will place the next largest element.

We compare the elements pointed to by the two pointers and place the larger one at the current position in nums1. We then move the corresponding pointer and repeat this process until all elements from nums2 have been merged into nums1.

And we’re done!

Solution in Python


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.
        """
        p = len(nums1) - 1
        m -= 1
        n -= 1

        while m >= 0 and n >= 0:
            if nums1[m] > nums2[n]:
                nums1[p] = nums1[m]
                m -= 1
            else:
                nums1[p] = nums2[n]
                n -= 1
            p -= 1

        while m >= 0:
            nums1[p] = nums1[m]
            m -= 1
            p -= 1

        while n >= 0:
            nums1[p] = nums2[n]
            n -= 1
            p -= 1

Complexity

  • Time: $O(m + n)$
    Since we are iterating through both arrays once, the time complexity is linear with respect to the total number of elements in both arrays.

  • Space: $O(1)$
    Since we are merging the arrays in place and not using any additional data structures that scale with input size, the space complexity is constant.

And we are done.