Skip to main content

88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array

Python​

Merge and sort​

  • Time: O((n+m)log(n+m))
  • Space: O(n)
from typing import List


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        if not nums2:
            return

        for i in range(m, len(nums1)):
            nums1[i] = nums2.pop()

        nums1.sort()

Two pointers​

  • Time: O(m+n)
  • Space: O(m+n)
from collections import deque


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.
        """
        queue1 = deque(nums1[:m])
        queue2 = deque(nums2)

        for cur in range(m+n):
            if queue1 and queue2:
                nums1[cur] = queue1.popleft() if queue1[0] <= queue2[0] else queue2.popleft()
                continue

            if queue1:
                nums1[cur] = queue1.popleft()

            if queue2:
                nums1[cur] = queue2.popleft()