Merging Two Sorted Arrays with O(1) Extra Space
Wed Mar 06 2024 mergeNoSpace :
Method to merge two sorted arrays into a single sorted array without using additional space. The technique involves comparing elements from the end of the first array and the beginning of the second array, ensuring that each element from the second array is placed in its correct position in the first array. This method efficiently handles the merging process by utilizing the existing space within the given arrays, showcasing an optimal approach to merging sorted arrays with constant space complexity.
1let arr1 = [10]
2let arr2 = [2, 3]
3
4let arr3 = [1, 5, 9, 10, 15, 20]
5let arr4 = [2, 3, 8, 13]
6
7
8function mergeNoSpace(arr1, arr2) {
9 let m = arr1.length
10 let n = arr2.length
11 for(let i = n - 1; i >= 0; i--){
12 let last = arr1[m - 1];
13 let j;
14 for(j=m - 2; j>=0 && arr1[j] > arr2[i]; j--){
15 arr1[j+1] = arr1[j];
16
17 }
18 if (last > arr2[i]){
19 arr1[j+1] = arr2[i]
20 arr2[i] = last
21 }
22 }
23 return [...arr1, ...arr2]
24}
25
26console.log(mergeNoSpace(arr1,arr2))
27console.log(mergeNoSpace(arr3,arr4))