Merge Without Extra Space

Given two sorted arrays a[] and b[] in non-decreasing order. 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.

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 5 10 12 18 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⁷

Approach 01:

#include <vector>
#include <algorithm>

class Solution {
 public:
  void mergeArrays(std::vector<int>& array1, std::vector<int>& array2) {
    int array1Length = array1.size();
    int array2Length = array2.size();

    int array1Index = array1Length - 1;
    int array2Index = 0;

    while (array1Index >= 0 && array2Index < array2Length) {
      if (array1[array1Index] >= array2[array2Index]) {
        // Swap elements between array1 and array2
        std::swap(array1[array1Index], array2[array2Index]);
        array1Index--;
        array2Index++;
      } else {
        break;
      }
    }

    // Sort both arrays
    std::sort(array1.begin(), array1.end());
    std::sort(array2.begin(), array2.end());
  }
};

class Solution:
    def mergeArrays(self, array1, array2):
        array1Length = len(array1)
        array2Length = len(array2)

        array1Index = array1Length - 1
        array2Index = 0

        while array1Index >= 0 and array2Index < array2Length:
            if array1[array1Index] >= array2[array2Index]:
                array1[array1Index], array2[array2Index] = array2[array2Index], array1[array1Index]
                array1Index -= 1
                array2Index += 1
            else:
                break

        array1.sort()
        array2.sort()

Time Complexity

• Swapping Elements:
  • The `while` loop iterates as long as there are elements to compare and swap between the two arrays.
  • The loop runs at most \(\min(n, m)\), where \(n\) and \(m\) are the lengths of `array1` and `array2`, respectively. This takes \(O(\min(n, m))\).
• Sorting:
  • After swapping, both arrays are individually sorted.
  • Sorting `array1` takes \(O(n \log n)\), and sorting `array2` takes \(O(m \log m)\).
• Overall Time Complexity:

  The total time complexity is \(O(n \log n + m \log m)\), dominated by the sorting steps.

Space Complexity

• In-Place Operations:
  • The swapping of elements between `array1` and `array2` is performed in-place, requiring \(O(1)\) extra space.
• Sorting Auxiliary Space:
  • Sorting both arrays may require \(O(n)\) and \(O(m)\) additional space, depending on the sorting algorithm used (e.g., quicksort or mergesort).
• Other Variables:
  • Variables like `array1Index`, `array2Index`, and loop variables require \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n + m)\), dominated by the sorting auxiliary space.