Merge Sorted Array(#88)
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
We explored three approaches:
Approach 1 – Brute Force:**
Copy all elements of nums2 into nums1 starting after the first m valid elements. Then, sort the entire nums1 array.
Approach 2 – Optimized with Temp Array:**
Copy the first m elements of nums1 into a temporary array. Use two pointers to merge this temp array and nums2 back into nums1 in sorted order.
Approach 3 – Optimal In-place (Two Pointers from End):**
Start filling nums1 from the back. Use two pointers at the end of the valid parts of nums1 and nums2. Place the larger of the two elements at the current back position, and move pointers accordingly. This avoids any extra space.
💻 Code
// 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);
};
// 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++];
};
// 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