88. Merge Sorted Array (Array, Two Pointers, Sorting)

링크 - https://leetcode.com/problems/merge-sorted-array/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

3가지 접근방식이 있다.

1) Merge and Sort

단순히 nums1에 nums2를 다 집어넣고 nums1을 sorting하는 것이다. 따라서 Time Complexity는 O((n+m)log(n+m))이 나오게 된다. 

2) Three Pointers(Start From the Beginning)

이미 nums1과 nums2가 Sorting이 되어있기 때문에, two pointers방식을 사용하여 O(n+m) time complexity로 풀 수 있다. 

알고리즘은 다음과 같다.

1. nums1을 nums1Copy에 복사를 한다.

2. 두개의 포인터를 사용해서 nums1Copy과 nums2의 값을 비교하며 작은 값을 nums1에 넣고 그 index를 증가시킨다.

Time Complexity: O(n+m). copy에 m번, for문에서 n+m번 읽고 쓰기 때문에 O(n+m)이다.

Space Complexity: O(m). copy에 m번

3) Three Pointers (Start From the End)

우리는 두번째 접근법에서 Space Complexity가 O(m)이 나왔기에, 이를 O(1)으로 줄여볼 생각을 해봐야 한다. 

사실 이미 nums1은 m+n의 크기를 가지고 있고 뒤에는 0으로 초기화가 되어 있기에, 뒤에서부터 쓰면 되지 않을까? 하는 생각을 해볼 수 있다.

따라서 알고리즘은 다음과 같다.

1. i1 과 i2를 각각 m-1, n-2로 설정하고 i를 m+n-1부터 시작하게 한다.

2. i1과 i2의 인덱스에 해당되는 값들을 nums1에 집어넣고 해당되는 인덱스를 1씩 빼간다.

Time Complexity: O(n+m). for문에서 n+m번 읽고 쓰기 때문에 O(n+m)이다.

Space Complexity: O(1).

Code

# Two Pointers (Start From the Beginning)
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.
        """
        nums1_copy = nums1[:m]

        i1 = 0
        i2 = 0

        for i in range(n+m):
            if i2 >= n or (i1 < m and nums1_copy[i1] <= nums2[i2]):
                nums1[i] = nums1_copy[i1]
                i1 += 1
            else:
                nums1[i] = nums2[i2]
                i2 += 1
            
# Three Pointers (Start From the End)
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.
        """
        i1 = m-1
        i2 = n-1

        for i in range(n+m-1, -1, -1):
            if i2 < 0:
                break

            if i1 >= 0 and nums1[i1] > nums2[i2]:
                nums1[i] = nums1[i1]
                i1 -= 1
            else:
                nums1[i] = nums2[i2]
                i2 -= 1