## DEV Community is a community of 890,178 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Swapnil Gupta

Posted on

# 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).

## Discussion (1)

Kishore kunal • Edited on

*my 2 cents:
*

PSEUDO CODE:

while (i ,j>=0):
nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--]
----The left nums2

while(j>=0):
nums1[k--] = nums2[j--]