Merge Sorted Array
(#88), Easy
Category: Array, Two Pointer, Sorting
Problem Statement
You are given two integer arrays `nums1` and `nums2`, both sorted in non-decreasing order. You are also given two integers `m` and `n`, representing the number of valid elements in `nums1` and `nums2` respectively. You need to merge `nums2` into `nums1` so that `nums1` becomes a single sorted array. The merge should be done **in-place**, meaning no extra array should be returned or used for final output. **Note:** `nums1` has a total length of `m + n`, with the first `m` elements being valid and the last `n` elements set as 0 placeholders. `nums2` has exactly `n` elements.
Examples
Input: nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Input: nums1 = [1], m = 1
nums2 = [], n = 0
Output: [1]
Input: nums1 = [0], m = 0
nums2 = [1], n = 1
Output: [1]
Approach
Approach 1: Brute Force
- Copy all elements of `nums2` into `nums1` starting from index `m`.
- Sort the entire `nums1` array to get the final result.
// Brute Force
var merge = function (nums1, m, nums2, n) {
for (let i = m, j = 0; i < m + n; i++, j++) {
nums1[i] = nums2[j];
}
nums1.sort((a, b) => a - b);
};Approach 2: Optimized with Temp Array
- Copy the first `m` elements of `nums1` into a temporary array.
- Use three pointers: `i` for temp, `j` for `nums2`, and `k` for position in `nums1`.
- Compare and merge elements back into `nums1` in sorted order.
- Fill any remaining elements from temp or `nums2`.
// Optimized with Temp Array
var merge = function (nums1, m, nums2, n) {
let arr = nums1.slice(0, m);
let i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (arr[i] <= nums2[j]) {
nums1[k++] = arr[i++];
} else {
nums1[k++] = nums2[j++];
}
}
while (i < m) nums1[k++] = arr[i++];
while (j < n) nums1[k++] = nums2[j++];
};Approach 3: Optimal In-place (Two Pointers from End)
- Set pointers `i = m - 1`, `j = n - 1`, and `k = m + n - 1`.
- Compare `nums1[i]` and `nums2[j]` from the end, place the larger at `nums1[k]`.
- Move the pointer that gave the larger value and decrement `k`.
- Continue until all elements of `nums2` are placed in `nums1`.
// Optimal In-place (Two Pointers from End)
var merge = function(nums1, m, nums2, n) {
let i = m - 1;
let j = n - 1;
let k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
};Complexity
Time: O(m + n) — each element is visited once
Space: O(1) — no extra space used in the final solution