Leetcode 88. Merge Sorted Array

Explanation

The problem is to merge two sorted integer arrays nums1 and nums2 into a single sorted array. It has been mentioned that array nums1 will have an adequate size to hold all elements from both initial arrays.

The approach is simple:

• We start from the end of both arrays and continuously pick the largest number to fill nums1's back positions.
• We compare the last element of nums1 and nums2, place the larger one at the end of nums1 (the end index is m + n - 1), then move the pointer of the nums array having larger element towards the left.
• This process continues till we have exhausted all elements of nums2.

walking through a given example:

Starting nums1 = [1,2,3,0,0,0], with m = 3

And nums2 = [2,5,6], n = 3,

The last element in nums1 is 3 and in nums2 is 6, since 6 > 3, we place 6 at the position 5 (index 5 = m+n-1) in nums1. Similarly, we compare 3 with 5 and place 5 at position 4 in nums1, afterwards, we compare 3 with 2, since 3 > 2, we place 3 at position 3 in nums1, and eventually place 2 at position 2 in nums1. Hence, th merged array would be [1,2,2,3,5,6].

python

1
2python
3class Solution:
4    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
5        while m > 0 and n > 0:
6            if nums1[m-1] >= nums2[n-1]:
7                nums1[m+n-1] = nums1[m-1]
8                m -= 1
9            else:
10                nums1[m+n-1] = nums2[n-1]
11                n -= 1
12        if n > 0:
13            nums1[:n] = nums2[:n]

java

1
2java
3class Solution {
4  public void merge(int[] nums1, int m, int[] nums2, int n) {
5    while (m > 0 && n > 0) {
6      if (nums1[m-1] > nums2[n-1]) {
7        nums1[m+n-1] = nums1[m-1];
8        m--;
9      } else {
10        nums1[m+n-1] = nums2[n-1];
11        n--;
12      }
13    }
14    while (n > 0) {
15       nums1[m+n-1] = nums2[n-1];
16       n--;
17    }
18  }
19}

javascript

1
2javascript
3var merge = function(nums1, m, nums2, n) {
4    while (n-- > 0) {
5        if (m <= 0 || nums2[n] >= nums1[m-1]) {
6            nums1[m+n] = nums2[n];
7        } else {
8            nums1[m+n] = nums1[--m];
9            n++;
10        }
11    }
12};

c++

1
2c++
3class Solution {
4public:
5  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
6    int i = m - 1;      
7    int j = n - 1;      
8    int k = m + n - 1;  
9    while (j >= 0){
10      if (i >= 0 && nums1[i] > nums2[j]){
11        nums1[k--] = nums1[i--];
12      }else{
13        nums1[k--] = nums2[j--];
14      }
15    }
16  }
17};

c#

1
2csharp
3public class Solution {
4    public void Merge(int[] nums1, int m, int[] nums2, int n) {
5        int i = m-1, j = n-1, tar = m+n-1;
6        while(j>=0) {
7            if(i>=0 && nums1[i] > nums2[j]) {
8                nums1[tar--] = nums1[i--];
9            }
10            else {
11                nums1[tar--] = nums2[j--];
12            }
13        }
14    }
15}

In python, java, c++ and c#, the solution are quite similar. JavaScript solution is a bit unique. The inner condition checks whether every element in nums1 is greater than the last element of nums2, if it's true, assign the element to nums1 and move one step towards the start of nums1, otherwise assign the element from nums2 and check the next element in nums2.

As seen, the process is continuing till every element in nums2 is processed, resulting in a merged sorted array.These simple and efficient solutions with providing a time complexity of O(m+n) using in-place algorithm is ideal for most real-world applications where the merging of two sorted lists is a common requirement.

When integrating these solutions within your code, ensure that the concept of arrays (or lists) and loops is clear. Understanding these basics will ensure that you can adapt the given solutions for different data sets and requirements.

In summary, the solutions provided use the core programming concept of looping through arrays/lists along with an understanding of indices to successfully merge sorted arrays in a range of languages including Python, Java, Javascript, C++, and C#. It's a common pattern that you will come across regularly in your coding journey, and mastering it will give a solid tool in your programming toolkit.

Last but not least, leveraging the language documentation and debugging tools can help you better understand and improve these solutions for your specific needs.