Day-18 Merge Sorted Array

Background

This problem statement is a part of the Introduction to Data Structures Fun with arrays-101 on leetcode. Under the sub-heading Inserting the Items into an Array.

Problem Statement

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

Note:

1. The number of elements initialized in nums1 and nums2 are m and n respectively.
2. You may assume that nums1 has enough space (size that is greater or 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]

Solution approach 1

Case 1: nums1[i] < nums2[j]

• Compare one element each from both the arrays. If element in 1st array is less then the element in 2nd array. Insert the element to array 3. Increment the counter i of array 1 by 1.

Case 2: nums2[j] < nums1[i]

• If element in array 2 is less than element in array 1. Then insert the element in array 3. Increment the counter j of array 2 to the next element.

Case 3: nums1[i] == nums2[j]

• Insert nums2[j] in array 3. Increment both counter i and j by 1.

As a result, array 3 would be the final merge sorted array.

Things to observe

1. We are using an extra array. Array 3, that means extra space. As asked in the question. The solution needs to be an in-place solution.
2. Notice that the skeleton code below mentions no return type. Hence, even though nums3 is the merged sorted array. It cannot be returned.

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.
        """
        i = 0
        j = 0 
        nums3 = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            elif nums1[i] > nums2[j]:
                nums3.append(nums2[j])
                j += 1
            elif nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                nums3.append(nums2[j])
                j += 1

        while i < m:
            nums3.append(nums1[i])
            i += 1

        while j < n:
            nums3.append(nums2[j])
            j += 1

Solution approach 2

1. Keep the merging logic same.
2. Instead of returning nums3. We can do item assignment. And, copy all the elements of nums3 to nums1.

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.
        """
        i = 0
        j = 0 
        nums3 = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            elif nums1[i] > nums2[j]:
                nums3.append(nums2[j])
                j += 1
            elif nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                nums3.append(nums2[j])
                j += 1

        while i < m:
            nums3.append(nums1[i])
            i += 1

        while j < n:
            nums3.append(nums2[j])
            j += 1


        for i in range(0, len(nums1)):
            nums1[i] = nums3[i]

Learnings

1. We have been able to merge the two sorted array.
2. Time complexity - O(n)
3. Time complexity of append - O(1)
4. As all values of nums1 itself are changed. So, there is no need to return anything. Hence, the solution is accepted.
5. List.insert might not be the way out. The reason being it is a built-in function. Secondly, insertion in at defined index adds on to the time complexity.

Things to figure out

• The solution needs to be an in-place solution. That is no extra memory needs to be used. How to solve it without using any extra space?
• Will optimizing on space complexity lead to increased time complexity?