Merge Sorted Array

Problem link: https://leetcode.com/problems/merge-sorted-array/
solution video: https://youtu.be/hVl2b3bLzBw , by Striver, TakeUForward
Solution:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
      int i= m-1;
      int j= n-1;
      int k= m+n-1;
     while(i>=0 && j>=0){
      //nums2[j] is larger value so it will go at k 
            if(nums1[i]<nums2[j]){
                nums1[k--] = nums2[j--];
            }else{
                nums1[k--] = nums1[i--];
            }
        }
        //If length of nums2 is more than length of nums1
        while(j>=0){
            nums1[k--] = nums2[j--];
        }
    }
}

one approach is to create the two pointer to arrays, whether start from beginning or from the end. We will use to insert the array elements from back, as array is already sorted so easier to put large elements at the back of the array.

Approach: We will create two pointers to compare the elements of the array of nums1[] and nums2[], which is i and j, and there would be third pointer k, which is set on nums1[], where we have to insert the elements at. So the pointer values will be -

i= m-1; j= n-1; k=m+n-1;

we will compare nums1[i] with nums2[j], out of these one element will be larger, whichever is the larger, we will insert our that element at k pointer index, and decrement the larger valued pointer and k pointer by 1, keeping the smaller pointer at same place.

we will keep doing for a loop until either j or i becomes 0,so the whole operation will be performed under while(j>=0|| i>=0)

The Traps:

• you may not set index properly, you will get array out of bounds errors.
• post assignment operator of the index: nums1[k] = nums2[j]; k--; j--; can be written as: nums1[k--] = nums2[j--]; as the operation will be completed first i.e. nums1[k] = nums2[j] then there will be decrement in 'k' and 'j' as this is post decrement.

• use if-else, instead of creating other loop or else you will end up exceeding the time complexity limit.
  The time complexity of this algorithm: O(n+m), as we are inserting k elements

• There may be the chances that one of the array will not end up earlier so to handle that we may add extra lines of code:
  

while(i>=0){
nums1[k--]= nums1[i--];
}
while(j>=0){
nums1[k--]= nums2[j--];
}

In this particular problem you need not to create a new array as nums1[] has already given enough space to fill the elements from nums2[], so the space complexity O(1).