Merge Sorted Array — Day 20(Python)

Image for post
Image for post
Photo by Clayton Cardinalli on Unsplash

Today we will be looking into one of the easy tagged questions from leetcode. The problem is on the topic “arrays”. Let us look into the question without wasting much time.

88. Merge Sorted Array

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.

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

According to the question, we have two sorted arrays, and we are required to merge in such a way that the output is a sorted array too. Notice that array1 has space allocated for array2, which means that we do not have to create a different array to store results. Instead, perform the operations on array1 itself. Along with the array itself, we have the size of the array too as input.

How can we make use of these inputs and find an optimized solution?

One of the ways to find a solution to this problem is to create an empty list.
Initialize pointers to the first index of both the array.
Compare the elements at the index of both the pointers.
Append the element with a lower value to the output list and increment the pointer of that array by 1.
On completing all the elements, copy the elements in the output to array1.

The code snippet would look like below.

class Merger:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
output = []
first = 0
second = 0
while(first < m and second < n):
if nums1[first] <= nums2[second]:
output.append(nums1[first])
first += 1
else:
output.append(nums2[second])
second += 1
while(first < m):
output.append(nums1[first])
first += 1
while(second < n):
output.append(nums2[second])
second += 1
nums1[:] = output[:]

Complexity analysis

Time Complexity

We are required to traverse through both the array to identify which number is to be inserted in the output array. Hence time complexity would be O(m+n).

Space Complexity

We are using additional space to store the result array, and hence, the space complexity is O(m+n).

Wait, we are not supposed to use any additional space. How do we avoid using a result array? Can we try searching for the larger number from the end of the arrays?

Since we know the size of the original arrays, let us have two pointers that start from the end of the array.
Check for larger among both the numbers, that number will be placed at the end of the array1. Decrease the pointer size by one.
Repeat the procedure until both the pointers reach the start of the array.

class Merger:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i = m -1
j = n -1
count = m+n-1
while( i >=0 and j >= 0):
if(nums1[i] > nums2[j]):
nums1[count] = nums1[i]
i -= 1
else:
nums1[count] = nums2[j]
j -= 1
count -= 1
nums1[:j+1] = nums2[:j+1]

Complexity analysis

Time Complexity

We are required to traverse through both the array to identify which number is to be inserted at the end of the array. Hence time complexity would be O(m+n).

Space Complexity

Since we are not using any extra data structure for storing data, except for the pointers, the space complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store