Friedrich Ewald My Personal Website

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]:
        p1 += 1
        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)).

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.