Merge Sorted Array

Patrick Leaton
Published: Feb. 25, 2021, 3:41 a.m.
Problem Description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example:

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

Output: [1,2,2,3,5,6]

Constraints:

  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1.length == m + n
  • nums2.length == n

 

The description was taken from https://leetcode.com/problems/merge-sorted-array/.

Problem Solution

#O(M + N) Time, O(1) Space
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        pointer_one, pointer_two = m - 1, n - 1
        pointer_three = len(nums1) - 1

        while pointer_one >= 0 and pointer_two >= 0:
            if nums2[pointer_two] > nums1[pointer_one]:
                nums1[pointer_three] = nums2[pointer_two]
                pointer_two -= 1
            else:
                nums1[pointer_three] =  nums1[pointer_one]
                pointer_one -= 1
            pointer_three -= 1

        for i in range(pointer_two + 1):
            nums1[i] = nums2[i]

Problem Explanation

We can solve this problem by using three pointers to traverse both arrays from the end to the beginning. 

The third pointer will act as a placeholder for the maximum between the other two pointers and once we place a pointer's number, we will move that pointer to the left.  This will continue until one of the pointers has gone past the beginning of its array.

We are basically building an array backward using each current maximum value.

Let's start by setting these pointers.  We will need to subtract the first two pointers by one since arrays begin at zero.

        pointer_one, pointer_two = m - 1, n - 1
        pointer_three = len(nums1) - 1

 

Once we set our pointers, we will create a loop that will run while both of the first two pointers are in bounds of their arrays.

        while pointer_one >= 0 and pointer_two >= 0:

 

During each iteration, we will check if the element at pointer two is greater than the element at pointer one.

If so, we will place the element from pointer two into pointer three's place then move this pointer to the left.

            if nums2[pointer_two] > nums1[pointer_one]:
                nums1[pointer_three] = nums2[pointer_two]
                pointer_two -= 1

 

If the element at pointer two is less than or equal to the element at pointer one, we will place the element at pointer one in the index at pointer three instead and move this pointer instead.

            else:
                nums1[pointer_three] =  nums1[pointer_one]
                pointer_one -= 1

 

We will decrement pointer three after each iteration so that we place one element per iteration.

            pointer_three -= 1

 

Once we have broken out of the loop, it means that one of the pointers has moved past index zero and has been decremented to a negative one.

When this happens, we can iterate up to pointer two, inclusively, and place each number from the second array into the beginning of the first.

This will yield two scenarios:

  1. Pointer one went past the beginning of its array so the remaining elements that need to be placed at the beginning of the output array are everything up to pointer two.

  2. Pointer two went past the beginning of its array, in which case this loop won't actually terminate and the elements that need to be placed within this same output array are already there.

        for i in range(pointer_two + 1):
            nums1[i] = nums2[i]