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.
1using System;
2
3public class MergeSortedArray {
4 public static void Merge(int[] nums1, int m, int[] nums2, int n) {
5 int i = m - 1, j = n - 1, k = m + n - 1;
6 while (i >= 0 && j >= 0) {
7 nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
8 }
9 while (j >= 0) {
10 nums1[k--] = nums2[j--];
11 }
12 }
13
14 public static void Main() {
15 int[] nums1 = {1, 2, 3, 0, 0, 0};
16 int[] nums2 = {2, 5, 6};
17 Merge(nums1, 3, nums2, 3);
18 Console.WriteLine(string.Join(", ", nums1));
19 }
20}
21The C# approach is similar to other languages, using attributes inherent in arrays to minimize copy operations. The solution iteratively decides the larger element and places it correctly.
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.