This content originally appeared on Level Up Coding - Medium and was authored by Leonard Yeo
Problem
Given two sorted arrays, merge them into a sorted manner.
Examples
- Example 01
Input: arr1 = [3, 5, 6, 10], arr2 = [1, 2, 7, 8, 11, 12]
Output: arr3 = [1, 2, 3, 5, 6, 7, 8, 10, 11, 12]
- Example 02
Input: arr1 = [1, 3, 4, 5], arr2 = [2, 4, 6, 8]
Output: arr3 = [1, 2, 3, 4, 4, 5, 6, 8]
- Example 03
Input: arr1 = [5, 8, 9], arr2 = [4, 7, 8]
Output: arr3 = [4, 5, 7, 8, 8, 9]
Solution 01
Pseudocode
- Create an array arr3 by concatenatingarr1 and arr2.
- Sort arr3 .
Source code
def merge(num1, num2):
arr3 = num1+num2
arr3.sort()
return arr3
arr1 = [3, 5, 6, 10]
arr2 = [1, 2, 7, 8, 11, 12]
assert merge(arr1, arr2) == [1, 2, 3, 5, 6, 7, 8, 10, 11, 12]
arr1 = [1, 3, 4, 5]
arr2 = [2, 4, 6, 8]
assert merge(arr1, arr2) == [1, 2, 3, 4, 4, 5, 6, 8]
arr1 = [5, 8, 9]
arr2 = [4, 7, 8]
assert merge(arr1, arr2) == [4, 5, 7, 8, 8, 9]
Time and Space Complexity
- Time Complexity: O((N+M)log(N+M)). Given N is the number of elements in arr1 and M is the number of elements in arr2 .
- Space Complexity: O(N+M)
Solution 02
Pseudocode
- Create an array arr3 of length/size arr1 + arr2 .
- Simultaneously traverse arr1 and arr2.
- Pick smaller of current elements in arr1 and arr2 , copy this smaller element to the next position in arr3 and move ahead in arr3 and the array whose element is picked.
3. If there are remaining elements in arr1 or arr2 , copy them in arr3 .
Source code
def merge(num1, num2):
arr3 = [None]*(len(num1)+len(num2))
i, j, k = 0, 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
arr3[k] = arr1[i]
k += 1
i += 1
else:
arr3[k] = arr2[j]
k += 1
j += 1
while i < len(num1):
arr3[k] = arr1[i];
k += 1
i += 1
while j < len(num2):
arr3[k] = arr2[j];
k += 1
j += 1
return arr3
arr1 = [3, 5, 6, 10]
arr2 = [1, 2, 7, 8, 11, 12]
assert merge(arr1, arr2) == [1, 2, 3, 5, 6, 7, 8, 10, 11, 12]
arr1 = [1, 3, 4, 5]
arr2 = [2, 4, 6, 8]
assert merge(arr1, arr2) == [1, 2, 3, 4, 4, 5, 6, 8]
arr1 = [5, 8, 9]
arr2 = [4, 7, 8]
assert merge(arr1, arr2) == [4, 5, 7, 8, 8, 9]
Time and Space Complexity
- Time Complexity: O(N+M). Given N is the number of elements in arr1 and M is the number of elements in arr2 .
- Space Complexity: O(N+M)
Takeaways
Thank you for reading this short problem solving question. If anyone knows a better or faster time complexity to solve this question, feel free to comment and feedback. Peace! ✌️
Merge Two Sorted Arrays in Python was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Leonard Yeo
Leonard Yeo | Sciencx (2022-03-18T12:08:25+00:00) Merge Two Sorted Arrays in Python. Retrieved from https://www.scien.cx/2022/03/18/merge-two-sorted-arrays-in-python/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.