Problem Statement
Given two sorted arrays nums1 of size m+n and nums2 of size n, where nums1 holds m valid elements followed by n zeros, merge nums2 into nums1 so the result is a single sorted array stored entirely inside nums1.
Example 1
Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Output: [1, 2, 2, 3, 5, 6]
Explanation: The valid elements of nums1 are [1, 2, 3] and nums2 is [2, 5, 6]. After merging all six values in sorted order, nums1 becomes [1, 2, 2, 3, 5, 6].
Example 2
Input: nums1 = [4, 5, 6, 0, 0, 0], m = 3, nums2 = [1, 2, 3], n = 3
Output: [1, 2, 3, 4, 5, 6]
Explanation: Every element of nums2 is smaller than every element of nums1. All three of nums2's values shift in front of nums1's values to produce [1, 2, 3, 4, 5, 6].
Brute Force Approach
The trailing zeros at the end of nums1 are placeholders deliberately sized to fit nums2 exactly. The simplest thing to do is fill those slots by copying every element of nums2 into them, giving you all m+n elements sitting together inside nums1. At that point the array is unsorted, so you just call sort on the whole thing. Think of it like sliding a second stack of papers into the blank pages at the back of a binder and then re-ordering everything from scratch. It is correct but ignores the fact that both halves were already sorted, you throw away that structure entirely.
Algorithm
Copy every element of nums2 into the trailing slots of nums1 starting at index m.
Sort the entire nums1 array of size m+n using the standard sort function.
nums1 now contains the fully merged sorted result.
Dry Run
Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* * Merges nums2 into nums1 in-place using a reverse two-pointer * approach, filling from the back of nums1 toward the front. */ void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { // p1 points to the last valid element of nums1 int p1 = m - 1; // p2 points to the last element of nums2 int p2 = n - 1; // p points to the last slot of nums1 (the fill position) int p = m + n - 1; // Fill nums1 from the back until nums2 is exhausted while (p2 >= 0) { /* nums1 still has elements and its current is larger */ if (p1 >= 0 && nums1[p1] > nums2[p2]) { nums1[p] = nums1[p1]; p1--; } /* nums2's current element is larger or equal */ else { nums1[p] = nums2[p2]; p2--; } // Move the fill pointer one step back p--; } }};/* Driver Code */int main() { vector<int> nums1 = {1, 2, 3, 0, 0, 0}; int m = 3; vector<int> nums2 = {2, 5, 6}; int n = 3; Solution sol; sol.merge(nums1, m, nums2, n); /* Print the merged sorted array */ cout << "Merged Array: "; for (int x : nums1) { cout << x << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O((m+n) log(m+n)) Copying nums2 into nums1 takes O(n). Sorting the combined array of size m+n dominates at O((m+n) log(m+n)).
Space Complexity: O(1) No extra data structures are allocated. Everything operates directly on nums1 in-place.
Optimal Approach
The key insight is that the largest elements should be placed last. Both nums1 and nums2 are sorted, so the largest element overall must be either the last valid element of nums1 or the last element of nums2. Instead of fighting for space at the front, start placing elements from the back of nums1 where there is free room. Maintain three pointers one at the last valid element of nums1, one at the last element of nums2, and one at the last slot of nums1. At each step, compare what the first two pointers see and place the larger value at the third pointer's position, then retreat that pointer. This way you never overwrite anything you still need, and the entire merge happens in one clean backwards sweep with no extra space needed.
Algorithm
Set pointer p1 to index m minus one, pointing at the last valid element of nums1.
Set pointer p2 to index n minus one, pointing at the last element of nums2.
Set pointer p to index m plus n minus one, pointing at the last slot of nums1.
While p2 is greater than or equal to zero, repeat the following steps.
If p1 is greater than or equal to zero and the element at p1 is greater than the element at p2, place the element at p1 into position p, then decrement both p1 and p.
Otherwise place the element at p2 into position p, then decrement both p2 and p.
When p2 drops below zero, all elements of nums2 have been placed and any remaining elements of nums1 are already in their correct positions, so the merge is complete.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* * Merges nums2 into nums1 in-place using a reverse two-pointer * approach, filling from the back of nums1 toward the front. */ void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { // p1 points to the last valid element of nums1 int p1 = m - 1; // p2 points to the last element of nums2 int p2 = n - 1; // p points to the last slot of nums1 (the fill position) int p = m + n - 1; // Fill nums1 from the back until nums2 is exhausted while (p2 >= 0) { /* nums1 still has elements and its current is larger */ if (p1 >= 0 && nums1[p1] > nums2[p2]) { nums1[p] = nums1[p1]; p1--; } /* nums2's current element is larger or equal */ else { nums1[p] = nums2[p2]; p2--; } // Move the fill pointer one step back p--; } }};/* Driver Code */int main() { vector<int> nums1 = {1, 2, 3, 0, 0, 0}; int m = 3; vector<int> nums2 = {2, 5, 6}; int n = 3; Solution sol; sol.merge(nums1, m, nums2, n); /* Print the merged sorted array */ cout << "Merged Array: "; for (int x : nums1) { cout << x << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(m+n) Each element from nums1 and nums2 is placed exactly once. The while loop runs at most m+n times where m and n are the number of valid elements in nums1 and nums2 respectively.
Space Complexity: O(1) Only three integer pointer variables are used. The merge happens entirely in-place inside nums1 with no extra data structures.
Interview follow-up Questions
Filling from the front would overwrite valid elements of nums1 before they have been compared and placed. Filling from the back uses the guaranteed empty trailing slots first, so no element is lost before being examined.
Be the first to add a comment.