Merge Two Sorted Arrays in Java with Explanation | LeetCode Solution

Merge Two Sorted Array LeetCode problem solution in Java with Explanation

Problem Description :-

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

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m+n such that it has enough space to hold additional elements from nums2.

Example 1 :-

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

Example 2 :-

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Lets see solution :-

Solution 1 :-

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

Explanation :-

Here, we have two array as nums1 and nums2, and its size in m and n. We have to assume that nums1 array size is equal to nums1 + nums2 length size. and both array are sorted and we have to merge nums2 array into nums1 array with sorting position.

We check both arrays value one by one from last element. Because both arrays are sorted.

1. First we check m and n if both are greater than 0 then go to while condition. 
2. Now check, both array's last value. Which one is greater. If nums1 array's last value is greater than nums2 array last value then it goes to if condition. And store nums1 array last value into nums1 array's last position. (Last position is equal to m+n, that is equal to nums1 + nums2 arrays length). And decrease the m value by 1.
   
3. If nums2 array's last value is greater than nums1 array's last value then we store nums2 last position value into nums1 array's last position. And decrease the n by 1.
4. These while loop continue until m or n not become 0.
5. In second while loop, we simply check if n is still not 0 then store nums2 array values into nums1 array one by one.

Example :-

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

• m and n both are greater than 0,
• nums1[m-1] means nums1[2] = 3 is greater than nums2[n-1] means nums2[2] = 6. Here 3 is not greater than 6. So it goes to else condition.
• nums1[m+n-1] = nums2[n-1], means nums1[5] = nums2[2]. So we store 6 value into nums1 array's last position at 5.
  Now n--, it becomes 2.
  nums1 = [1, 2, 3, 0, 0, 6], n = 2, m = 3.
  
• nums1[2] > nums2[1],  3 > 5, No it goes to else condition.
• nums1[4] = nums2[1]. Store 5 value to nums1 array's 4th position.
  Now n--, it becomes 1.
  nums1 = [1, 2, 3, 0, 5, 6], n = 1, m = 3.
  
• nums1[2] > nums2[0],  3 > 2, Yes
  
• nums1[3] = nums1[2], Store 3 value to nums1 array's 3rd position.
  Now m--, it becomes 2.
  nums1 = [1, 2, 3, 3 , 5, 6], n = 1, m = 2.
  
• nums1[1] > nums2[0],  2 > 2, No it goes to else condition.
• nums1[2] = nums2[0], Store 2 value to nums1 array's 2nd position.
  Now n--, it becomes 0.
  nums1 = [1, 2, 2, 3, 5, 6], n = 0, m = 2.
• Now n is become 0, first while loop done.
• In second while loop, n is not greater than 0 so it does not go into while loop.
• So we get our Final output in nums1 array as [1, 2, 2, 3, 5, 6].

 

Happy Coding.

Other LeetCode Problem and Solution in Java with Explanation.

• Duplicate each occurrence of zeros in Array with Explanation | Java Solution  
• Find Squares of a Sorted Array in Java | LeetCode Java Solution