Merge Without Extra Space | GFG | LeetCode | Solution

 Statement - Given two sorted arrays arr1[] and arr2[] of sizes n and m in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.

 

Example 1:

Input: 
n = 4, arr1[] = [1 3 5 7] 
m = 5, arr2[] = [0 2 6 8 9]
Output: 
arr1[] = [0 1 2 3]
arr2[] = [5 6 7 8 9]
Explanation:
After merging the two 
non-decreasing arrays, we get,  

Problem Link - Click

Code - Time Complexity O((m+n)log(max(m, n))) and Space Complexity O(1).

class Solution{

    public:

        void merge(long long arr1[], long long arr2[], int n, int m) 

        { 

            // code here    

            int f = n -1;

            int l = 0;

            while(f >= 0 && l < m)

            {

                if(arr1[f] >= arr2[l])

                {

                    swap(arr1[f], arr2[l]);

                }

                f--;

                l++;

            }   

            sort(arr1, arr1 + n);

            sort(arr2, arr2 + m);

        } 

};