[LeetCode] 88. Merge Sorted Array

leetcode

I think this is pretty straightforward. Use a pointer to find the position for elements in nums2 array to insert. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        i = 0
        for num in nums2:
            # find pos in nums1
            while i <= m:
                if i == m:
                    # end, append
                    nums1.insert(i, num)
                    m += 1
                    del nums1[-1]
                    break
                if nums1[i] < num:
                    i += 1
                    continue
                # nums1[i] >= n, insert number
                nums1.insert(i, num)
                m += 1
                del nums1[-1]
                break

However, this is not the fastest because every time we need to push back the array to insert, also, del in Python is O(n) operation. How can we improve?
We can utilize the empty space left in nums1 array and compare from the back. Also, this solution is more generalized because the previous one is only for 2 array, but this works for multiple arrays. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        i = m - 1
        j = n - 1
        pos = m + n - 1
        while i >= 0 and j >=0:
            if nums1[i] > nums2[j]:
                nums1[pos] = nums1[i]
                pos -= 1
                i -= 1
            else:
                nums1[pos] = nums2[j]
                pos -= 1
                j -= 1
        # if there's still nums2 left
        while j >= 0:
            nums1[pos] = nums2[j]
            pos -= 1p
            j -= 1