Sponsored
Sponsored
The most efficient way to merge two sorted arrays without using extra space is by using a two-pointer approach from the end. You start comparing elements from the end of both arrays and fill `nums1` from the back. This way you avoid needing additional space for a temporary array and can overwrite existing data in `nums1`.
Time Complexity: O(m + n); Space Complexity: O(1) since we do not use extra space.
1function merge(nums1, m, nums2, n) {
2 let i = m - 1, j = n - 1, k = m + n - 1;
3 while (i >= 0 && j >= 0) {
4 nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
5 }
6 while (j >= 0) {
7 nums1[k--] = nums2[j--];
8 }
9}
10
11let nums1 = [1, 2, 3, 0, 0, 0];
12let nums2 = [2, 5, 6];
13merge(nums1, 3, nums2, 3);
14console.log(nums1);
15JavaScript solution works similarly to other languages in using a decrementing pointers approach to efficiently merge the sorted arrays directly in `nums1`.
This is a less efficient approach that involves first combining the contents of `nums1` and `nums2` into a new array. Then, the new array is sorted, and its contents are copied back into `nums1`. Although straightforward, this approach involves extra memory allocation.
Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) additional space aside from function call stack during sorting.
1
In C, we first append the elements of `nums2` onto `nums1`, and then employ the Quick Sort function `qsort` to sort the entire array.