Leetcode: Merge sorted array
Given two lists or arrays, nums1
and nums2
as well as two integers m
and n
which give the length of the arrays nums1
and nums2
respectively. nums1
should be modified in place.
The first idea that came to my mind was a merge-sort. Given that those initial arrays are already sorted, I could have two pointers and iterate over both arrays simulatenously, copying the values into a third one. The problem here is that the array should be modified in place. The way to achieve this in O(2(n+m)) => O(n+m)
is to iterate over the temporary array and write it back to the initial array.
The code is listed below.
from typing import List, Optional
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.
"""
p1 = 0
p2 = 0
t = []
while p1 < m and p2 < n:
if nums1[p1] < nums2[p2]:
t.append(nums1[p1])
p1 += 1
else:
t.append(nums2[p2])
p2 += 1
t += nums1[p1:m]
t += nums2[p2:]
for i in range(len(t)):
nums1[i] = t[i]
if __name__ == '__main__':
s = Solution().merge
l = [1,2,3,0,0,0]
s(l, 3, [2,5,6], 3)
print(l, [1,2,2,3,5,6])
Runtime: 68 ms, faster than 28.82% of Python3 online submissions for Merge Sorted Array. Memory Usage: 13.9 MB, less than 85.86% of Python3 online submissions for Merge Sorted Array.Looking at the solutions from others I saw that they simply called the
sort
function. This is obviously less code to write but more time-consuming since the complexity is O((n+m)*log(n+m))
.