Lam Nguyen

January 20, 2024

 • 1 min read

0

88. Merge Sorted Array

Leetcode 88 Merge two sorted array solution with Python 3

Description

• You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
• Merge nums1 and nums2 into a single array sorted in non-decreasing order.
• The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Solution:

• Initialize last variable: last = m + n - 1

• Loop over two arrays nums1 and nums2 (m > 0 and n > 0):

  • If last element of nums1 nums1[m-1] greater then last element of nums2 nums2[n-2]:
    • Assign nums1[last] = nums1[m-1]
    • Decrease m: m -= 1
  • else:
    • Assign nums1[last] = nums2[n-1]
    • Decrease n: n -= 1
  • Decrease last -= 1

• If there is still element remaining in nums2. Loop over nums2 (n > 0):

  • Assign nums1[last] = nums2[n-1]
  • Decrease n -= 1
  • Decrease last -= 1

Big(O):

• Time O(m+n) | space O(1)

Code:

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    last = m + n - 1
    while m > 0 and n > 0:
        if nums1[m - 1] > nums2[n - 1]:
            nums1[last] = nums1[m - 1]
            m -= 1
        else:
            nums1[last] = nums2[n - 1]
            n -= 1
        last -= 1

    while n > 0:
        nums1[last] = nums2[n - 1]
        n -= 1
        last -= 1