Day 7 - Merge Without Extra Space.md

Difficulty	Source	Tags
Hard	160 Days of Problem Solving	Sorting Mathematical

🚀 Day 7. Merge Without Extra Space 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given two sorted arrays a[] and b[] in non-decreasing order, merge them in sorted order without using any extra space.
Modify a[] to contain the first n smallest elements, and modify b[] to contain the remaining m elements in sorted order.

🔍 Example Walkthrough:

Input:
a[] = [2, 4, 7, 10], b[] = [2, 3]
Output:
a[] = [2, 2, 3, 4]
b[] = [7, 10]

Explanation:
After merging, the sorted order is [2, 2, 3, 4, 7, 10].
The first n elements go into a[], and the remaining elements go into b[].

Input:
a[] = [1, 5, 9, 10, 15, 20], b[] = [2, 3, 8, 13]
Output:
a[] = [1, 2, 3, 5, 8, 9]
b[] = [10, 13, 15, 20]

Explanation:
After merging, the sorted order is [1, 2, 3, 5, 8, 9, 10, 13, 15, 20].

Constraints:

• 1 <= a.size(), b.size() <= 10^5
• 0 <= a[i], b[i] <= 10^7

🎯 My Approach:

This problem can be solved using the Gap Algorithm, which reduces the need for extra space while efficiently merging two sorted arrays.

Steps:

1. Calculate Initial Gap:

   • Combine the sizes of both arrays, n + m, and compute the initial gap as (n + m) // 2 + (n + m) % 2.

2. Iterative Comparison:

   • Using the gap, compare elements in both arrays. Swap them if they are out of order.
   • Reduce the gap in each iteration until it becomes 0.

3. Handle Overlapping Cases:

   • Handle cases where elements of a[] need to be swapped with b[].

4. Ensure Final Order:

   • After processing, the arrays will be modified in-place to reflect the merged sorted order.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O((n + m) * log(n + m))

  • The gap reduces logarithmically with each iteration (log(n + m) iterations).
  • Each iteration performs comparisons and swaps in O(n + m).
  • Hence, the total complexity is O((n + m) * log(n + m)).

• Expected Auxiliary Space Complexity: O(1)

  • No extra space is used; modifications are done in-place.

📝 Solution Code

Code (C)

void mergeArrays(int* a, int n, int* b, int m) {
    int gap = n + m;
    int nextGap(int gap) {
        return (gap <= 1) ? 0 : (gap / 2) + (gap % 2);
    }

    for (gap = nextGap(gap); gap > 0; gap = nextGap(gap)) {
        int i, j;

        for (i = 0; i + gap < n; i++) {
            if (a[i] > a[i + gap]) {
                int temp = a[i];
                a[i] = a[i + gap];
                a[i + gap] = temp;
            }
        }
        for (j = (gap > n ? gap - n : 0); i < n && j < m; i++, j++) {
            if (a[i] > b[j]) {
                int temp = a[i];
                a[i] = b[j];
                b[j] = temp;
            }
        }
        for (j = 0; j + gap < m; j++) {
            if (b[j] > b[j + gap]) {
                int temp = b[j];
                b[j] = b[j + gap];
                b[j + gap] = temp;
            }
        }
    }
}

Code (C++)

class Solution {
public:
    int nextGap(int gap) {
        return (gap <= 1) ? 0 : (gap / 2) + (gap % 2);
    }

    void mergeArrays(vector<int>& a, vector<int>& b) {
        int n = a.size(), m = b.size(), gap = n + m;

        for (gap = nextGap(gap); gap > 0; gap = nextGap(gap)) {
            int i, j;

            for (i = 0; i + gap < n; i++) {
                if (a[i] > a[i + gap]) swap(a[i], a[i + gap]);
            }

            for (j = (gap > n ? gap - n : 0); i < n && j < m; i++, j++) {
                if (a[i] > b[j]) swap(a[i], b[j]);
            }

            for (j = 0; j + gap < m; j++) {
                if (b[j] > b[j + gap]) swap(b[j], b[j + gap]);
            }
        }
    }
};

Code (Java)

class Solution {
    private int nextGap(int gap) {
        return (gap <= 1) ? 0 : (gap / 2) + (gap % 2);
    }
    public void mergeArrays(int[] a, int[] b) {
        int n = a.length, m = b.length;
        int gap = n + m;

        for (gap = nextGap(gap); gap > 0; gap = nextGap(gap)) {
            int i, j;
            for (i = 0; i + gap < n; i++) {
                if (a[i] > a[i + gap]) {
                    int temp = a[i];
                    a[i] = a[i + gap];
                    a[i + gap] = temp;
                }
            }
            for (j = (gap > n ? gap - n : 0); i < n && j < m; i++, j++) {
                if (a[i] > b[j]) {
                    int temp = a[i];
                    a[i] = b[j];
                    b[j] = temp;
                }
            }
            for (j = 0; j + gap < m; j++) {
                if (b[j] > b[j + gap]) {
                    int temp = b[j];
                    b[j] = b[j + gap];
                    b[j + gap] = temp;
                }
            }
        }
    }
}

Code (Python)

class Solution:
    def nextGap(self, gap):
        return 0 if gap <= 1 else (gap // 2) + (gap % 2)

    def mergeArrays(self, a, b):
        n, m = len(a), len(b)
        gap = n + m

        while gap > 0:
            gap = self.nextGap(gap)
            i, j = 0, 0

            while i + gap < n:
                if a[i] > a[i + gap]:
                    a[i], a[i + gap] = a[i + gap], a[i]
                i += 1

            j = max(gap - n, 0)
            i = 0 if gap > n else n - gap
            while i < n and j < m:
                if a[i] > b[j]:
                    a[i], b[j] = b[j], a[i]
                i += 1
                j += 1
            j = 0
            while j + gap < m:
                if b[j] > b[j + gap]:
                    b[j], b[j + gap] = b[j + gap], b[j]
                j += 1

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count