Problem Statement : Given Two sorted Array Arr1[] and Arr2[] of size n and m in non decreasing order .Merge them in sorted order. 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 4 8 10] m = 5, Arr2[] = [2 3 9] Output: Arr1[] = [1 2 3 4] Arr2[] = [8 9 10] Explanation: After merging the two non-decreasing arrays, we get, 1,2,3,4,8,9,10. Example2: 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 :
दो Non-decreasing array को मिलाने के बाद, हमें 0 1 2 3 5 6 7 8 9 मिलता है।
Solution 1 : Brute Force Method Apply करने पर -
Intuition :
हम एक नई m+n size की array use कर सकते है , उसके बाद इसमें array1 and array 2 के elements डालकर उन्हें sort करते है। sort करने के बाद उसमे array1 और array2 के all elements present हो।
Approach:
एक array3 create करो जिसकी size m+n हो।
array1 and array2 के सभी elements को array3 में put कर देते है
अब array3 को sort करते है।
अब पहले array1 को fill करते है उसके बाद remaining elements को array2 में fill करते है।
Output :
Before merge
1 4 7 8 10
2 3 9
After merge :
1 2 3 4 7
8 9 10
Time complexity : O(n*log(n))+O(n)+O(n)
Space Complexity : O(n)
Solution2 : Without Using Space
Intuition:
हम arr1 में Iterating के बारे में सोच सकते हैं और जब भी encounter किसी ऐसे elements से होता है जो arr2 के first element से बड़ा होता है, तो बस इसे Swap करें।
अब arr2 को sorted manner से rearrange करें, loop के complete होने के बाद हमें दोनों array के elements non-decreasing order में मिलेंगे।
Approach :
Array1 में एक for loop का use करते है
जब भी array1 में कोई ऐसा element मिलता है ,जिसकी value array2 के first elements से ज्यादा हो तो उनको Swap कर देते है।
Array2 को Re-arrange करते है।
इस process ko repeat करते रहते है
C++ Code .
#include<bits/stdc++.h>
using namespace std;
void merge(int arr1[], int arr2[], int n, int m) {
int arr3[n+m];
int k = 0;
for (int i = 0; i < n; i++) {
arr3[k++] = arr1[i];
}
for (int i = 0; i < m; i++) {
arr3[k++] = arr2[i];
}
sort(arr3,arr3+m+n);
k = 0;
for (int i = 0; i < n; i++) {
arr1[i] = arr3[k++];
}
for (int i = 0; i < m; i++) {
arr2[i] = arr3[k++];
}
}
int main() {
int arr1[] = {1,4,7,8,10};
int arr2[] = {2,3,9};
cout<<"Before merge:"<<endl;
for (int i = 0; i < 5; i++) {
cout<<arr1[i]<<" ";
}
cout<<endl;
for (int i = 0; i < 3; i++) {
cout<<arr2[i]<<" ";
}
cout<<endl;
merge(arr1, arr2, 5, 3);
cout<<"After merge:"<<endl;
for (int i = 0; i <5; i++) {
cout<<arr1[i]<<" ";
}
cout<<endl;
for (int i = 0; i < 3; i++) {
cout<<arr2[i]<<" ";
}
}