If you want to master array manipulation, “Merge Without Extra Space” is an essential coding problem! In this blog, we\u2019ll 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.<\/p>\n\n\n\n
Given two sorted arrays a[]<\/strong> and b[] <\/strong>of size n <\/strong>and m <\/strong>respectively, the task is to merge them in sorted order without using any extra space<\/strong>. Modify a[]<\/strong> so that it contains the first n<\/strong> elements and modify b[]<\/strong> so that it contains the last m<\/strong> elements.<\/p>\n\n\n\n Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Examples:<\/strong><\/p>\n\n\n\n Constraints:<\/strong> Let\u2019s solve the problem step by step in the simplest way:<\/p>\n\n\n\n This approach is easy to understand but does not meet the “no extra space” requirement.<\/p>\n\n\n\nInput<\/strong>: a[] = [2, 4, 7, 10], b[] = [2, 3]\nOutput<\/strong>:
2 2 3 4
7 10\nExplanation<\/strong>: After merging the two non-decreasing arrays, we get, 2 2 3 4 7 10<\/pre>\n\n\n\nInput<\/strong>: a[] = [1, 5, 9, 10, 15, 20], b[] = [2, 3, 8, 13]\nOutput<\/strong>:
1 2 3 5 8 9
10 13 15 20\nExplanation<\/strong>: After merging two sorted arrays we get 1 2 3 5 8 9 10 13 15 20.\n<\/pre>\n\n\n\nInput<\/strong>: a[] = [0, 1], b[] = [2, 3]\nOutput<\/strong>:
0 1
2 3\nExplanation<\/strong>: After merging two sorted arrays we get 0 1 2 3.<\/pre>\n\n\n\n
1 <= a.size(), b.size() <= 105<\/sup>
0 <= a[i], b[i] <= 107<\/sup><\/p>\n\n\n
\n\n\n\nBrute Force Solution<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Use a new array to merge both arrays like in merge sort.<\/li>\n\n\n\n
After merging, copy the first part back to\u00a0arr1<\/code>\u00a0and the remaining to\u00a0arr2<\/code>.<\/li>\n\n\n\n
We use extra space to make merging easy, then distribute the sorted elements back.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n