If you want to master array manipulation, “Merge Without Extra Space” is an essential coding problem! In this blog, we’ll explain the problem, show you both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.
Given two sorted arrays a[] and b[] of size n and m respectively, the task is to merge them in sorted order without using any extra space. Modify a[] so that it contains the first n elements and modify b[] so that it contains the last m elements.
Here’s the [Problem Link] to begin with.
Examples:
Input: a[] = [2, 4, 7, 10], b[] = [2, 3] Output:
2 2 3 4
7 10 Explanation: After merging the two non-decreasing arrays, we get, 2 2 3 4 7 10
Input: a[] = [1, 5, 9, 10, 15, 20], b[] = [2, 3, 8, 13] Output:
1 2 3 5 8 9
10 13 15 20 Explanation: After merging two sorted arrays we get 1 2 3 5 8 9 10 13 15 20.
Input: a[] = [0, 1], b[] = [2, 3] Output:
0 1
2 3 Explanation: After merging two sorted arrays we get 0 1 2 3.
Constraints:
1 <= a.size(), b.size() <= 105
0 <= a[i], b[i] <= 107
Brute Force Solution
Intuition and Approach
Let’s solve the problem step by step in the simplest way:
- Merge into a Third Array:
Use a new array to merge both arrays like in merge sort. - Copy Back:
After merging, copy the first part back toarr1
and the remaining toarr2
. - Why does this work?
We use extra space to make merging easy, then distribute the sorted elements back.
This approach is easy to understand but does not meet the “no extra space” requirement.
Code Implementation
from typing import List
class Solution:
def mergeArrays(self, arr1, arr2):
n, m = len(arr1), len(arr2)
arr3 = [0] * (n + m) # create a new array to hold all elements
left = 0
right = 0
index = 0
# merge both arrays into arr3
while left < n and right < m:
if arr1[left] <= arr2[right]:
arr3[index] = arr1[left]
left += 1
index += 1
else:
arr3[index] = arr2[right]
right += 1
index += 1
# copy remaining elements from arr1
while left < n:
arr3[index] = arr1[left]
left += 1
index += 1
# copy remaining elements from arr2
while right < m:
arr3[index] = arr2[right]
right += 1
index += 1
# copy back to arr1 and arr2
for i in range(n + m):
if i < n:
arr1[i] = arr3[i]
else:
arr2[i - n] = arr3[i]
PythonCode Explanation
- We create a new array
arr3
to hold all elements. - We merge both arrays into
arr3
using two pointers. - After merging, we copy the first
n
elements back toarr1
and the rest toarr2
.
Dry Run
Input:arr1 = [1]
arr2 =
- Merge into
arr3
:[1]
- Copy back:
arr1 = [1]
arr2 =
Time and Space Complexity
- Time Complexity: O(n + m)
We traverse both arrays once. - Space Complexity: O(n + m)
We use extra space for the merged array.
Conclusion
The brute force approach is simple but does not meet the requirement of “no extra space.” It’s good for understanding the merging process.
Optimal Solution
Intuition and Approach
Now, let’s solve the problem without using extra space:
- Swap and Sort:
Start from the end ofarr1
and the start ofarr2
. If an element inarr1
is greater than an element inarr2
, swap them. - Sort Both Arrays:
After swapping, sort both arrays to make sure all elements are in order. - Why does this work?
By always moving the largest elements to the end and smallest to the beginning, we ensure both arrays are sorted after the final sort.
This approach is efficient and meets the problem’s requirements.
Code Implementation
class Solution:
def mergeArrays(self, arr1, arr2):
n, m = len(arr1), len(arr2)
left = n - 1 # pointer at end of arr1
right = 0 # pointer at start of arr2
# swap elements if arr1[left] > arr2[right]
while left >= 0 and right < m:
if arr1[left] > arr2[right]:
arr1[left], arr2[right] = arr2[right], arr1[left]
left -= 1
right += 1
else:
break
arr1.sort() # sort arr1
arr2.sort() # sort arr2
PythonCode Explanation
- We use two pointers: one at the end of
arr1
and one at the start ofarr2
. - If
arr1[left]
is greater thanarr2[right]
, we swap them and move the pointers. - After all necessary swaps, we sort both arrays.
Dry Run
Input:arr1 = [1]
arr2 =
- Compare and swap:
- Swap 7 and 0 →
arr1 = [1]
,arr2 =
- Swap 5 and 2 →
arr1 = [1]
,arr2 =
- Swap 3 and 7 → no swap needed, break
- Swap 7 and 0 →
- Sort both arrays:
arr1 = [1]
arr2 =
Time and Space Complexity
- Time Complexity: O((n + m) log(n + m))
Due to the final sort of both arrays. - Space Complexity: O(1)
No extra space used.
Conclusion
The optimal solution is efficient and meets the “no extra space” requirement. It’s the best approach for interviews and large datasets.
Final Thoughts
The “Merge Without Extra Space” problem is a great way to learn about in-place array manipulation. Start with brute force to understand the basics, then use the optimal solution for best performance.