So here is my chain of thought: 1. First and most direct approach was to create a new array and populate it, taking smallest element from both arrays in turn, moving cursors in both arrays. Then I've noticed that the question insentifies solving the task "in place", using free space in first array. 2. This "in place" approach did not allow us to start from the smallest numbers and go up. The main goal is to move all elements from the 2nd array to the first. If we go from smallest numbers we will have to insert elements from the 2nd array in the middle of the 1st, and to do so we will have to move all remaining elements of the 1st array to free up space for the new element with complexity of O(n * m), too slow. So, we can just start from the end of the arrays. We have empty space at the end of the first array and can take biggest element from the both arrays in turn, inserting element from the 2nd array or moving element from the middle of the 1st array. This will give the linear complexity of O(n + m). In my solution there is a way to improve, but it works good enough.
Suggestion. Explain how you got to your answer. Most people would think to add the smartest elements at the front. Instead of starting by adding the largest at the back of the array.
So here is my chain of thought:
1. First and most direct approach was to create a new array and populate it, taking smallest element from both arrays in turn, moving cursors in both arrays. Then I've noticed that the question insentifies solving the task "in place", using free space in first array.
2. This "in place" approach did not allow us to start from the smallest numbers and go up. The main goal is to move all elements from the 2nd array to the first. If we go from smallest numbers we will have to insert elements from the 2nd array in the middle of the 1st, and to do so we will have to move all remaining elements of the 1st array to free up space for the new element with complexity of O(n * m), too slow. So, we can just start from the end of the arrays. We have empty space at the end of the first array and can take biggest element from the both arrays in turn, inserting element from the 2nd array or moving element from the middle of the 1st array. This will give the linear complexity of O(n + m).
In my solution there is a way to improve, but it works good enough.
Suggestion. Explain how you got to your answer.
Most people would think to add the smartest elements at the front. Instead of starting by adding the largest at the back of the array.
Good idea, thank you!