leetcode 88:- Merge Sorted Array solution in java

Merge Sorted Array solution in java

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.

The problem is taken from the below mentioned link:- Merge Sorted Array Problem

Flow Diagram:-

Approach:-

Here we will use the two pointer logic. Here we have provided two already sorted arrays of nums1[] and nums2[]. And we have given the the m, which is the last already filled places for nums1[] and n, which is the size of nums2[]. And nums[1] has enough empty places so that we can store the final sorted array in nums1[].

If we take the example 1:-

nums1[]

1	2	3	0	0	0
Index 0	Index 1	Index 2	Index 3	Index 4	Index5

nums2[]

2	5	6
Index 0	Index 1	Index 2

Now two pointer is taken, i for the nums1[] and j for nums2[]. where starting value of them will be

i = m-1 = 2 and j = m-1 = 2. Now we will compare the corresponding array elements for the two given array at the index position 2. The larger one will be placed at the k position of the nums[1] which has a starting value of 5 in his case.

So for loop 1:-

As nums2[2]>nums1[2]

For loop 2:-

j = 1 , i = 2 , k = 4

As nums2[1] =5> nums1[2]=3

For loop 3:-

j = 0 , i = 2 , k =3

As nums2[0] =2< nums1[2]=3

Code:-

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

Code Snippest:-