88. Merge Sorted Array¶
Intitution¶
We are given two sorted arrays and need to merge them into nums1 in-place. Since nums1 has enough space at the end, we can start filling from the back to avoid overwriting existing values in nums1.
We merge from the back (from the largest index) — placing the largest elements first — so we always have space to write into.
Complexity¶
| Space Complexity | Time Complexity |
|---|---|
| $\(\text{O}(1)\)$ | $\(\text{O}(n)\)$ |
Code¶
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = nums1.length-1; i >=0; --i) {
if( (m-1 >= 0) && ( (n-1 < 0) || nums1[m-1] > nums2[n-1] ) ) {
nums1[i] = nums1[m-1];
m--;
} else {
nums1[i] = nums2[n-1];
n--;
}
}
}