Merge Without Extra Space – GeeksforGeeks Solution Explained

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() <= 10⁵
0 <= a[i], b[i] <= 10⁷

Brute Force Solution

Intuition and Approach

Let’s solve the problem step by step in the simplest way:

1. Merge into a Third Array:
   Use a new array to merge both arrays like in merge sort.
2. Copy Back:
   After merging, copy the first part back to arr1 and the remaining to arr2.
3. 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]

Code 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 to arr1 and the rest to arr2.

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:

1. Swap and Sort:
   Start from the end of arr1 and the start of arr2. If an element in arr1 is greater than an element in arr2, swap them.
2. Sort Both Arrays:
   After swapping, sort both arrays to make sure all elements are in order.
3. 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

Code Explanation

• We use two pointers: one at the end of arr1 and one at the start of arr2.
• If arr1[left] is greater than arr2[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
• 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.