LeetCode #88 Merge Sorted Array Solution & Explanation - Zyrastory

Content

Post Views: 1,870

LeetCode Problem

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.

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Solution

Please be adviced that the problem’s description- “The final sorted array should not be returned by the function, but instead be stored inside the array nums1″

C# Solution

Solution1

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        
        int cnt = 0;
        for(int i = m;i<nums1.Length;i++)
        {
            nums1[i] = nums2[cnt];
            cnt++;
        }
        Array.Sort(nums1);
    }
}

The time complexity should be : m-n times + Array.Sort ( based on Quicksort ) ➡ O(n)+O(n log n)

But look at the follow up : “Can you come up with an algorithm that runs in O(m + n) time?”

Maybe we should try another way?

⭐Solution2 (Recommend – two pointer solution)

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        
        int index = m+n-1;  //last index
        while(n>0)
        {
            if(m>0 && nums1[m-1]>nums2[n-1])
            {
                nums1[index] = nums1[m-1];
                m--;
            }
            else
            {
                nums1[index] = nums2[n-1];
                n--;
            }
            index --;
        }
    }
}

What we want to do is combine nums2 n element with nums1 m element to original nums1.

So if we want to combine and sort together, we need to compare the element of two array in iteration.

Time Complexity : O(m + n)

Java Solution

Solution1

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int cnt = 0;
        for(int i = m;i<nums1.length;i++)
        {
            nums1[i] = nums2[cnt];
            cnt++;
        }
        
        Arrays.sort(nums1); 
    }
}

Runtime : 1ms

⭐Solution2

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m+n-1;  //last index
        while(n>0)
        {
            if(m>0 && nums1[m-1]>nums2[n-1])
            {
                nums1[index] = nums1[m-1];
                m--;
            }
            else
            {
                nums1[index] = nums2[n-1];
                n--;
            }
            index --;
        } 
    }
}

Runtime : 0ms

Python3 Solution

Solution1

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.
        """
        cnt = 0;
        while(m < len(nums1)):
            nums1[m] = nums2[cnt];
            cnt+=1
            m+=1
        nums1.sort();

Runtime : 78ms、46ms、54ms ➡ average 59ms

⭐Solution2

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.
        """
        index = m+n-1
        
        while(n>0):
            if(m>0 and nums1[m-1]>nums2[n-1]):
                nums1[index] = nums1[m-1];
                m-=1;
            
            else:
                nums1[index] = nums2[n-1];
                n-=1;
            
            index -=1;

Runtime : 59ms、70ms、30ms ➡ average 53ms

JavaScript Solution

Solution1

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    var index = m+n-1;  //last index
    while(n>0)
    {
        if(m>0 && nums1[m-1]>nums2[n-1])
        {
            nums1[index] = nums1[m-1];
            m--;
        }
        else
        {
            nums1[index] = nums2[n-1];
            n--;
        }
        index --;
    } 
};

Runtime : 97ms、109ms、64ms

Conclusion

How to reduce time complexity always is a interesting question of coding.

In this case, you can use a iteration with two pointers to avoid using Array.sort function (List.sort…, etc)

"Eventually, all things merge into one, and a river runs through it."   
                                                                                              - Norman Maclean

The problem link : Merge Sorted Array – LeetCode

Reference

Array Sort time complexity – C# (reddit.com)

Technology Article

Related Post

LeetCode Problem

Solution

C# Solution

Java Solution

Python3 Solution

JavaScript Solution

Conclusion

Related Posts

LeetCode #70 Climbing Stairs Solution & Explanation

LeetCode #153 Find Minimum in Rotated Sorted Array Solution & Explanation

Leave a ReplyCancel Reply