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.
1import java.util.Arrays;
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(String[] args) {
15 int[] nums1 = {1, 2, 3, 0, 0, 0};
16 int[] nums2 = {2, 5, 6};
17 merge(nums1, 3, nums2, 3);
18 System.out.println(Arrays.toString(nums1));
19 }
20}
21The Java solution uses conditional statements to decide which element should be placed in `nums1`. The loop continues until both pointers have positioned all elements 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.