Leetcode - Merge Sorted Array

Leetcode : Merge Sorted Array

Description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Example

Input

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output

[1,2,2,3,5,6]

Approach

Use two pointers and compare the last elements of each arrays (as the arrays are sorted, last element is the largest of all). And substitute the last element of nums1 to the bigger number.

Solution (Python)

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        i = m - 1
        j = n - 1
        k = m + n - 1
        
        while i >= 0 and j >= 0:
            if nums1[i] < nums2[j]:
                nums1[k] = nums2[j]
                j = j - 1
            else:
                nums1[k] = nums1[i]
                i = i - 1
            k = k - 1
        
        if j >= 0:
            nums1[:k+1] = nums2[:j+1]
        
        return nums1
        

Result

Runtime: 24 ms
Memory Usage: 13.4 MB
Runtime Beats 73.13% of Python Submission