Problem of the day
Given two non-decreasing sorted arrays, ‘A’ and ‘B’, having ‘N’ and ‘M’ elements, respectively.
You must merge these arrays, ‘A’ and ‘B’, into a sorted array without using extra space. Of all the 'N + M' sorted elements, array 'A' should contain the first 'N' elements, and array 'B' should have the last 'M' elements.
You must perform the merge operation in place and must not allocate any extra space to merge the two arrays.
For example:
When ‘N’ = 4, ‘A’ = {1, 4, 5, 7} and ‘M’ = 3, ‘B’ = {2, 3, 6}.
We can merge these two arrays into {1, 2, 3, 4, 5, 6, 7} (The elements of ‘A’ are {1, 2, 3, 4} ).
Hence, the answer is {1, 2, 3, 4, 5, 6, 7}.
The first line contains two integers, ‘N’ and ‘M’, denoting the sizes of ‘A’ and ‘B’, respectively.
The second line contains ‘N’ integers denoting the elements of ‘A’.
The third line contains ‘M’ integers denoting the elements of ‘B’.
Output Format:
You must merge the two sorted arrays in place. The smallest ‘N’ elements should be in ‘A’, and the greatest ‘M’ elements should be in ‘B’. You don’t have to return anything. The system will print ‘A’ + ‘B’, where ‘+’ denotes concatenation.
3 4
1 8 8
2 3 4 5
1 2 3 4 5 8 8
We have ‘A’ = {1, 8, 8} and ‘B’ = {2, 3, 4, 5}.
Merging the two arrays results in {1, 2, 3, 4, 5, 8, 8}.
Hence the answer is {1, 2, 3, 4, 5, 8, 8}, where ‘A’ contains {1, 2, 3} and ‘B’ contains {4, 5, 8, 8}.
4 5
1 1 1 1
2 2 3 3 5
1 1 1 1 2 2 3 3 5
1 <= N <= 10^5
1 <= M <= 10^5
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
The sum of ‘N + M’ over all test cases does not exceed 2 * 10^5.
Time Limit: 1-sec
Think of a solution to pick the smallest ‘N’ numbers in ‘A’ and the remaining in ‘B’.
Approach:
We want to have the ‘N’ smallest elements in ‘A’. For the ‘ith’ smallest elements we can traverse over the remaining positions of ‘A’ and the array ‘B’ to find the minimum elements among them, and then swap that element with ‘A[i]’. Lastly, we sort the array ‘B’.
Algorithm:
Time Complexity:
O(N * (M + N) + MlogM), where ‘N’ is the size of ‘A’ and ‘M’ is the size of ‘B’.
We are traversing the array ‘A’ in O(N) time, and for each element in ‘A’ we are traversing over the remaining positions of ‘A’ and all positions of ‘B’ in O(N + M) time. The swapping operation takes O(1) time. Lastly, we sort the array ‘B’ in O(MlogM) time. Hence, the overall time complexity of the problem is O(N * (N + M) + MlogM).
Space Complexity:
O(1)
We are not utilizing any extra space, hence the overall space complexity of this solution is O(1).