Merge Sorted Array

97.4k
0

Given two sorted integer arrays nums1 and nums2, along with integers m and n, merge nums2 into nums1 so that nums1 becomes one sorted array.

  • The first m positions of nums1 contain valid sorted elements.

  • The last n positions of nums1 are reserved for the merge and should not be considered part of the initial data.

  • nums2 contains n sorted elements.

Modify nums1 in place so that it contains all m + n elements in non-decreasing order.

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, nums1 becomes [1, 2, 2, 3, 5, 6].

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0

Output: [1]

Explanation: nums2 is empty, so nums1 remains unchanged.

Brute Force Approach

The reserved positions at the end of nums1 provide enough space to copy all elements from nums2.

After copying, all required values are present in nums1, but their combined order may be incorrect. Sorting the complete array gives the required merged result.

Algorithm

  • Return immediately when n == 0 because nums1 already contains the final sorted array.

  • Traverse nums2 and copy each value into the reserved portion of nums1, beginning from index m.

  • After copying, all m + n required elements are present inside nums1.

  • Sort the complete nums1 array in non-decreasing order so the elements from both arrays appear in their correct positions.

  • Retain the sorted nums1 as the final merged array.

Dry Run

Merge Two Sorted Arrays Brute Force Approach Dry Run.png

Merge Two Sorted Arrays Brute Force Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Merges nums2 into nums1 by copying first and sorting afterward.
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// No merge is needed when nums2 has no elements.
if (n == 0) {
return;
}
// Copy nums2 into the reserved positions of nums1.
for (int i = 0; i < n; i++) {
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};
int main() {
vector<int> nums1 = {1, 2, 3, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
int m = 3;
int n = 3;
Solution solution;
solution.merge(nums1, m, nums2, n);
for (int value : nums1) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O((M + N) log(M + N)), because the complete array of M + N elements is sorted.

Space Complexity: Depends on the sorting implementation. If internal sorting memory is excluded, it may be described as O(1) auxiliary space, but library sorting can use additional stack or temporary memory.

Better Approach

Since both valid input portions are already sorted, sorting the complete combined array is unnecessary.

A normal merge can compare the smallest unprocessed elements from both arrays and place the smaller one into a temporary array. Temporary storage prevents valid values in nums1 from being overwritten before they are processed.

Algorithm

  • Initialize i = 0, j = 0, and index = 0 to traverse the first m elements of nums1, the n elements of nums2, and the temporary result.

  • Create a temporary array temp of size m + n so merged elements can be stored without overwriting unprocessed values in nums1.

  • While both arrays still contain unprocessed values, compare nums1[i] and nums2[j] and place the smaller value into temp[index].

  • Move the pointer belonging to the selected value and increment index after each placement.

  • When one array becomes exhausted, copy all remaining elements from the other array into temp.

  • Copy the complete temp array back into nums1.

Dry Run

Merge Two Sorted Arrays Better Appraoch Dry Run.png

Merge Two Sorted Arrays Better Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Merges both sorted arrays using temporary storage.
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> temp(m + n);
int i = 0;
int j = 0;
int index = 0;
// Compare the smallest unprocessed values from both arrays.
while (i < m && j < n) {
// Take nums1 value when it is the smaller one.
if (nums1[i] <= nums2[j]) {
temp[index++] = nums1[i++];
}
// Otherwise take the smaller value from nums2.
else {
temp[index++] = nums2[j++];
}
}
// Copy any valid nums1 elements that remain.
while (i < m) {
temp[index++] = nums1[i++];
}
// Copy any nums2 elements that remain.
while (j < n) {
temp[index++] = nums2[j++];
}
// Move the merged result back into nums1.
for (int k = 0; k < m + n; k++) {
nums1[k] = temp[k];
}
}
};
int main() {
vector<int> nums1 = {1, 2, 3, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
int m = 3;
int n = 3;
Solution solution;
solution.merge(nums1, m, nums2, n);
for (int value : nums1) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(M + N), because every element is processed during the merge and copied back at most once.

Space Complexity: O(M + N), because the temporary array stores the complete merged result.

Optimal Approach

Filling nums1 from the beginning could overwrite valid elements that have not been compared yet.

Instead, use the empty positions at the end. Since both arrays are sorted, their largest unprocessed values are at the ends. Compare these values and place the larger one into the last available position of nums1.

Working backward protects all unprocessed elements and removes the need for extra storage.

Algorithm

  • Initialize i = m - 1 and j = n - 1 to point to the largest valid elements of nums1 and nums2. Set k = m + n - 1 to the final position of nums1.

  • While both i and j remain valid, compare nums1[i] and nums2[j].

  • Place the larger value at nums1[k], since the last available position must contain the largest remaining element.

  • Move the pointer belonging to the selected value backward and decrement k.

  • If values remain in nums2, copy them into the remaining positions of nums1.

  • Any remaining values from the original nums1 require no movement because they are already in their correct positions.

Dry Run

Merge Two Sorted Arrays Optimal Approach Dry Run.png

Merge Two Sorted Arrays Optimal Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Merges both arrays in place by filling nums1 from the end.
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// nums1 already contains the final result when nums2 is empty.
if (n == 0) {
return;
}
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
// Place the largest remaining value at the last free position.
while (i >= 0 && j >= 0) {
// Take nums1 value when it is larger.
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
}
// Otherwise place the value from nums2.
else {
nums1[k--] = nums2[j--];
}
}
// Only nums2 leftovers need copying into nums1.
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
};
int main() {
vector<int> nums1 = {1, 2, 3, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
int m = 3;
int n = 3;
Solution solution;
solution.merge(nums1, m, nums2, n);
for (int value : nums1) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(M + N), where M and N represent the valid element counts in nums1 and nums2. Every value receives at most one comparison and one placement.

Space Complexity: O(1), because only three pointer variables require auxiliary storage.

FAQS

Q1. Why does the Brute Force Approach use a temporary array?

Temporary storage prevents valid values from being overwritten before comparison and allows a standard sorted merge.

Q2. Why does the Better Approach require complete sorting?

Copying nums2 into the reserved positions places all values inside nums1 but does not guarantee sorted order.

Q3. Why does the Optimal Approach merge from the end?

Backward placement uses the reserved positions first and protects unprocessed valid values inside nums1.

Q4. Why do remaining nums1 values require no copying?

Remaining nums1 values already occupy the earliest positions and remain smaller than every value placed later.

Q5. How does the algorithm handle duplicate values?

Every occurrence remains preserved. Equal values receive normal placement without removal.

Q6. What happens when m equals 0 or n equals 0?

When m equals 0, all nums2 values enter nums1. When n equals 0, nums1 already contains the final result.

Two PointerArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. tuf-examples-1 Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0