88. Merge Sorted Array -LC

https://leetcode.com/problems/merge-sorted-array/description

This is a well written problem with easy to understand sample cases.even though it is marked easy in LC i initially find it hard to wrap my head around the problem.

Key findings

• Its an array problem
• need to have in-place solution
• given arrays are sorted
• solve it in o(m+n)

Since the arrays are sorted two pointer approach is used for solving the problem.

Python3 – solution below

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.
        """
        i,j,k = m-1,n-1,len(nums1) -1 

        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -=1
            else:
                nums1[k] = nums2[j]
                j -=1
            k -=1
        if j >= 0:
            nums1[:j+1] = nums2[:j+1]

Here the two pointers are initiated with the last value of the array because the arrays are already sorted and we want to avoid moving all the value to the right position in the case if we insert the value of nums2 at the beginning of the array instead .

Edge conditions