Merge Sorted Array

Given two sorted arrays and their sizes , merge the two into the first sorted array.

Extra space equal to the size of the second array is provided at the end of the first array.

For example,

Given the arrays:

num1 = [1,2,3,0,0,0] , size = 3 ( remaining space for the second array to be merged)

num2 = [2,5,6] , size = 3

The output is :

num1 = [1,2,2,5,6]

Try out the solution here:

https://leetcode.com/problems/merge-sorted-array/

Solution:

Hint:

• Start from the end of the arrays

• Use three pointers , one to the end of the first array (original size), one to the end of the second array and one to the end of the first array (combined size of first and second array)

Algorithm:

1. Create three pointers as mentioned above
2. While the third pointer pointing to the last of the first array (combined size) and the second pointer pointing to the end of the second array is greater than or equal to zero, do the following:
   • Check if first pointer greater than or equal to zero and the number pointer by first pointer is greater than the number pointed by second pointer
     • If yes replace the number pointed by the third pointer by the number pointed by the first pointer and decrement both pointers
     • If no replace the number pointed by the third pointer by the number pointed by the second pointer and decrement both pointers

Here is the code:

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

In the while loop , we compare the third and second pointers but not the first pointer.

Why ?

Because if you have finished processing the elements in the second array then there is no need to proceed further.

All the elements are sorted and merged at this point.

On the contrary if first pointer reaches zero , that doesn’t mean the elements are merged and sorted.

Consider the below use case to understand this:

Let’s say the first array has elements all of which are greater than the elements in the second array.

In this case we will keep pushing the elements in the first array to its end and decrement the first pointer till it reaches 0.

At this point we have processed all the elements in the first array.

But still there are elements in the second array which we need to place it in the first array.

We will do them one by one decrementing the second pointer along the way.

Illustration:

Here is an illustration for the input :

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

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

First iteration:

First pointer = 2 (index starts from 0)

Second pointer = 2

Third pointer = 5

Now the number pointed by first pointer is less than the number pointed by the second pointer.

3 < 6

So we copy the value 6 to the third pointer element.

And then we decrement both the second pointer and the third pointer.

Now it looks like this:

Second iteration:

Now the number pointed by first pointer (3) is less than the number pointed by the second pointer (5)

So we copy the value pointed by second pointer to the third pointer element and decrement both the pointers.

Now it looks like this:

Third iteration

Now the element pointed by first pointer (3) is greater than the element pointed by the second pointer (2)

So we copy the value of first pointer element to the third pointer element and decrement both the pointers.

Fourth iteration

Now the element pointed by first pointer(2) is not greater than the element pointed by the second pointer(2).

So we copy the element pointed by second pointer to the element pointed by the third pointer.

And then we decrement both the second and third pointers.

At this point we have run out of elements in second array and there is no element left for comparison.

So we stop here.

And the elements are already merged and sorted:

[1,2,2,3,5,6]

The general idea is :

Compare the elements of the first array and the second array from the end.

Whichever is greater put them at the end of the first array.

Do this for each pair of elements (one from first array , another from second array).

Tip:

Whenever you are asked to find a solution using array data structure without using additional memory , consider scanning the array from the end.

Time complexity:

We go through each element so time complexity is O(m +n)

Space complexity:

We don’t use any extra space so space complexity is O(1)