ArrayProblem 12 of 36
Merge 2 sorted arrays without using Extra space
Problem Statement
Given two sorted arrays arr1 of size m and arr2 of size n, merge them such that after merging, arr1 contains the first m smallest elements and arr2 contains the remaining n elements, both in sorted order. Do this without using extra space.
Example:
- Input:
arr1 = [1, 4, 7, 8, 10],arr2 = [2, 3, 9] - Output:
arr1 = [1, 2, 3, 4, 7],arr2 = [8, 9, 10] - Explanation: Merged sorted array would be [1,2,3,4,7,8,9,10], first 5 go to arr1, last 3 to arr2
Approach 1: Using Extra Space (Brute Force)
Intuition
Create a temporary array, merge both arrays into it, then copy back.
Algorithm
- Create a temporary array of size m + n
- Use two pointers to merge both sorted arrays
- Copy first m elements to arr1, remaining n to arr2
java
public class Solution {
public void merge(int[] arr1, int[] arr2) {
int m = arr1.length;
int n = arr2.length;
int[] temp = new int[m + n];
int i = 0, j = 0, k = 0;
// Merge both arrays into temp
while (i < m && j < n) {
if (arr1[i] <= arr2[j]) {
temp[k++] = arr1[i++];
} else {
temp[k++] = arr2[j++];
}
}
while (i < m) temp[k++] = arr1[i++];
while (j < n) temp[k++] = arr2[j++];
// Copy back to original arrays
for (i = 0; i < m; i++) {
arr1[i] = temp[i];
}
for (i = 0; i < n; i++) {
arr2[i] = temp[m + i];
}
}
}Complexity Analysis
- Time Complexity: O(m + n) - Single merge pass
- Space Complexity: O(m + n) - Temporary array
Approach 2: Insertion Sort Style
Intuition
Compare the largest of arr1 with the smallest of arr2. If arr1's largest is greater, swap them and re-sort arr2.
Algorithm
- Compare
arr1[m-1]witharr2[0] - If
arr1[m-1] > arr2[0], swap them - Insert the swapped element at correct position in arr2 (maintain sorted order)
- Repeat until no more swaps needed
java
public class Solution {
public void merge(int[] arr1, int[] arr2) {
int m = arr1.length;
int n = arr2.length;
// Iterate through arr1 from end
for (int i = m - 1; i >= 0; i--) {
// If largest of arr1 > smallest of arr2, swap
if (arr1[i] > arr2[0]) {
int temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
// Re-sort arr2 using insertion sort logic
int first = arr2[0];
int k;
for (k = 1; k < n && arr2[k] < first; k++) {
arr2[k - 1] = arr2[k];
}
arr2[k - 1] = first;
}
}
}
}Complexity Analysis
- Time Complexity: O(m × n) - For each element in arr1, we might shift all elements in arr2
- Space Complexity: O(1) - No extra space
Approach 3: Gap Method / Shell Sort (Optimal)
Intuition
Use a gap-based approach similar to Shell Sort. Start with a large gap and reduce it, comparing and swapping elements that are 'gap' apart.
Algorithm
- Start with gap = ceil((m + n) / 2)
- Compare elements that are 'gap' apart
- If left > right, swap them
- Reduce gap = ceil(gap / 2)
- Repeat until gap becomes 0
java
public class Solution {
private int nextGap(int gap) {
if (gap <= 1) return 0;
return (gap / 2) + (gap % 2); // ceil(gap / 2)
}
public void merge(int[] arr1, int[] arr2) {
int m = arr1.length;
int n = arr2.length;
int gap = nextGap(m + n);
while (gap > 0) {
int i = 0;
// Comparing elements in arr1
while (i + gap < m) {
if (arr1[i] > arr1[i + gap]) {
int temp = arr1[i];
arr1[i] = arr1[i + gap];
arr1[i + gap] = temp;
}
i++;
}
// Comparing elements in arr1 and arr2
int j = gap > m ? gap - m : 0;
while (i < m && j < n) {
if (arr1[i] > arr2[j]) {
int temp = arr1[i];
arr1[i] = arr2[j];
arr2[j] = temp;
}
i++;
j++;
}
// Comparing elements in arr2
if (j < n) {
j = 0;
while (j + gap < n) {
if (arr2[j] > arr2[j + gap]) {
int temp = arr2[j];
arr2[j] = arr2[j + gap];
arr2[j + gap] = temp;
}
j++;
}
}
gap = nextGap(gap);
}
}
}Dry Run Example
arr1 = [1, 4, 7, 8, 10], arr2 = [2, 3, 9]
m = 5, n = 3, total = 8
Initial gap = ceil(8/2) = 4
Gap = 4:
Compare: arr1[0] vs arr1[4] → 1 vs 10 ✓
arr1[1] vs arr2[0] → 4 vs 2 → SWAP → arr1=[1,2,7,8,10], arr2=[4,3,9]
arr1[2] vs arr2[1] → 7 vs 3 → SWAP → arr1=[1,2,3,8,10], arr2=[4,7,9]
arr1[3] vs arr2[2] → 8 vs 9 ✓
arr1[4] vs - (out of range)
Gap = ceil(4/2) = 2:
Compare: arr1[0] vs arr1[2] → 1 vs 3 ✓
arr1[1] vs arr1[3] → 2 vs 8 ✓
arr1[2] vs arr1[4] → 3 vs 10 ✓
arr1[3] vs arr2[0] → 8 vs 4 → SWAP → arr1=[1,2,3,4,10], arr2=[8,7,9]
arr1[4] vs arr2[1] → 10 vs 7 → SWAP → arr1=[1,2,3,4,7], arr2=[8,10,9]
arr2[0] vs arr2[2] → 8 vs 9 ✓
Gap = ceil(2/2) = 1:
Compare all adjacent elements and fix remaining inversions...
Final: arr1=[1,2,3,4,7], arr2=[8,9,10]
Complexity Analysis
- Time Complexity: O((m+n) × log(m+n)) - Gap reduces by half each iteration
- Space Complexity: O(1) - No extra space used
Key Takeaways
- Gap method achieves O(1) space with O((m+n) log(m+n)) time
- The technique is inspired by Shell Sort
- Gap sequence: Start with ceil((m+n)/2), keep halving
- Three cases to handle: both in arr1, one in each, both in arr2
- This is one of the clever solutions that satisfies the "no extra space" constraint
- For interviews, clearly state the tradeoff between time and space complexity