Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Merge Without Extra Space – GeeksforGeeks Solution Explained
    Data Structures & Algorithms

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    codeanddebugBy codeanddebug7 July 2025No Comments5 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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

    Contents:
     [show]
    • Brute Force Solution
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Optimal Solution
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Final Thoughts

    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]
    Python

    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
    Python

    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.

    Array Hard
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleMerge Intervals | Leetcode 56 | Brute Force and Optimal
    Next Article Missing And Repeating – GeeksforGeeks Solution Explained
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025
    Data Structures & Algorithms

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025
    Data Structures & Algorithms

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (99)
      • Beginner (44)
      • Expert (28)
      • Intermediate (27)
    • Uncategorised (1)
    Recent Posts

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Intervals | Leetcode 56 | Brute Force and Optimal

    7 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.