Merge Sorted Arrays Without Extra Space
Hard Problems: Merge & Intervals DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Merging two sorted arrays without using extra space, Arrays, Sorting, Two Pointers, Time Complexity, Space Complexity, In-place Algorithm, Shell Sort, Merge Arrays, sorting algorithms, two pointer technique, time complexity analysis, array manipulation, Shell Sort.
Given two sorted arrays arr1 and arr2 of sizes n and m respectively, in non decreasing order. Merge them in sorted order such that arr1 contains the first n smallest elements and arr2 contains the remaining m elements. The arrays should be modified in place. Input Specification: n: size of arr1 m: size of arr2 arr1: a list of n integers, sorted in non decreasing order. arr2: a list of m integers, sorted in non decreasing order. Output Specification: The modified arr1 containing the n smallest elements. The modified arr2 containing the m largest elements. Sample Test Cases: Example 1: Input: n = 4, arr1 = [1, 4, 8, 10] m = 3, arr2 = [2, 3, 9] Output: arr1 = [1, 2, 3, 4] arr2 = [8, 9, 10] Explanation: After merging the two non decreasing arrays, we get: 1, 2, 3, 4, 8, 9, 10. The first 4 elements are moved to arr1 and the next 3 to arr2. Example 2: Input: n = 4, arr1 = [1, 3, 5, 7] m = 5, arr2 = [0, 2, 6, 8, 9] Output: arr1 = [0, 1, 2, 3] arr2 = [5, 6, 7, 8, 9] Explanation: After merging the two non decreasing arrays, we get: 0, 1, 2, 3, 5, 6, 7, 8, 9. The first 4 elements are moved to arr1 and the next 5 to arr2.