[LeetCode Solution] 88. Merge Sorted Array

Problem Description

LeetCode 88. Merge Sorted Array

Given two ascending order lists, merge them into a single sorted list. However, there is a condition: the sorting must be done in-place on the nums1 array.

Solution

Approach

1) Copy the nums2 array to the beginning of nums1 at positions 0, 0, and so on. 2) Sort the copied array using the sort() function.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:] = nums2[:] # [1,2,3,2,5,6],

        nums1.sort() # [1,2,3,2,5,6] #Tim sort O(nlogn)

The time and space complexity of the above solution are as follows:

• Time Complexity: O((m+n)log(m+n))
  • The sort() function in Python 3 uses Tim sort with a time complexity of O(nlogn). Thus, the overall time complexity is O(m+n).
• Space Complexity: O(1)
  • No additional space is used.