Merge Two Sorted Arrays Without Extra Space

Problem Statement: Given two sorted arrays arr1 and arr2 of sizes n and m, respectively, merge them in such a way that the resulting merged array is also sorted. Do not use any extra space.

Example

Input: arr1 = [1, 3, 5, 7], arr2 = [0, 2, 6, 8, 9]

Output:

arr1 = [0, 1, 2, 3]

arr2 = [5, 6, 7, 8, 9]

Solution:

To merge two sorted arrays without extra space, we can use a two-pointer technique along with swapping.

Steps to Solve:

1.    Initialize two pointers:

• i pointing to the last element of arr1.

• j pointing to the first element of arr2.

2.    While i is valid and j is valid:

• If arr1[i] is greater than arr2[j], swap them and adjust the pointers.

3.    Sort both arrays individually after the swapping process.

Time Complexity: O((n + m) log(n + m))

Space Complexity: O(1)