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.
1#include <stdio.h>
2
3void merge(int* nums1, int m, int* nums2, int n) {
4 int i = m - 1;
5 int j = n - 1;
6 int k = m + n - 1;
7
8 while (i >= 0 && j >= 0) {
9 if (nums1[i] > nums2[j]) {
10 nums1[k--] = nums1[i--];
11 } else {
12 nums1[k--] = nums2[j--];
13 }
14 }
15
16 while (j >= 0) {
17 nums1[k--] = nums2[j--];
18 }
19}
20
21int main() {
22 int nums1[] = {1, 2, 3, 0, 0, 0};
23 int nums2[] = {2, 5, 6};
24 merge(nums1, 3, nums2, 3);
25 for (int i = 0; i < 6; i++) {
26 printf("%d ", nums1[i]);
27 }
28 return 0;
29}This C implementation uses a two-pointer technique starting from the back of the arrays `nums1` and `nums2`. It compares elements of both arrays from the end and places the larger element at the current end position 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.