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.
1def merge(nums1, m, nums2, n):
2 i, j, k = m - 1, n - 1, m + n - 1
3 while i >= 0 and j >= 0:
4 if nums1[i] > nums2[j]:
5 nums1[k] = nums1[i]
6 i -= 1
7 else:
8 nums1[k] = nums2[j]
9 j -= 1
10 k -= 1
11 while j >= 0:
12 nums1[k] = nums2[j]
13 j -= 1
14 k -= 1
15
16nums1 = [1, 2, 3, 0, 0, 0]
17nums2 = [2, 5, 6]
18merge(nums1, 3, nums2, 3)
19print(nums1)
20This Python solution also uses the two-pointer approach to place each element. The list's end ensures no interference with unsorted elements during the process.
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.