2 pointers - 2
In the previous article, you've probably seen a trailer of how things look like in the case of 2-pointers. Let's warm up a bit more.
Mind you, the problem discussed below is an important one, and can be a sub-part in many different problems.
Merge 2 Sorted Arrays
The problem statement is that we're given 2 sorted arrays. We need to merge the elements of both arrays into a single array, and that, too, in a sorted order.
Example Inputs
array1 = [1, 5, 5, 10]
array2 = [2, 3, 6, 6, 6, 9]Example Resultant
[1, 2, 3, 5, 5, 6, 6, 6, 9, 10]One additional thing to notice is that in the problem, they've asked to merge the given arrays so that it's stored in the first array. Please refer to the problem statement for a detailed explanation.
How to Solve?
An approach could be to put all the elements from arr2 to the back of arr1 and then sort arr1 using the in-built sort function.
Implementation
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i = 0, j = m; i < n; ++i, ++j)
nums1[j] = nums2[i];
sort(nums1.begin(), nums1.end());
}Time & Space Complexity
Space Complexity: O(1) [assuming space complexity for sort to be O(1)]
Time Complexity: This heavily depends on the time complexity of the sort function. The in-built sort function works in O(NlogN) time when sorting N elements.
Therefore, time complexity = O((N+M)*Log(N+M))
Let's improve Time Complexity
Whenever struggling to improve the time complexity, do think of this that have you taken all the given constraints into consideration?
Hint 1
In the earlier approach, we didn't take this fact into consideration that the given arrays are already sorted.Hint 2
The first element in the final array will be either arr1[0] or arr2[0] (because these are the smallest ones).Now, let's say the smallest one is arr1[0], now the 2nd element in the final array will be either arr1[1] or arr2[0]
Hint 3
Try keeping 2 pointers, one for each of the input arrays. These will point to the smallest elements in the respective arrays that have not been added to the final sorted array yet. Try to think in this direction?Explanation
The idea is basically to have 2-pointers, i & j (both equal to 0, initially), one for arr1 and one for arr2:- arr1[i] represents the smallest element from arr1 which hasn't been pushed to the final array yet.
- Similarly, arr2[j] represents the smallest element from arr2 which hasn't been pushed to the final array yet.
The whole process will be as explained below:
- Initialise an empty aux vector, 2 integer pointers i and j, both initialised to 0.
-
Then start iterating while i < len(arr1) and j < len(arr2):
- If arr1[i] < arr2[j], then push back arr1[i] to aux and increment the value of i by 1.
- Otherwise, push back arr2[j] to aux and increment the value of j by 1.
- Now, after the above while loop, exactly 1 of the arrays out arr1 and arr2 will still have some remaining elements to be pushed to aux.
- So, we can add the remaining elements of both the arrays to aux. (We're adding both just because we don't know which one is remaining). An alternate approach could also be to check which one has remaining elements, and only add the elements from that array to the aux array.
- Now that we have our final aux array, all that's needed is to copy the elements from aux array to arr1, as expected in the problem statement.
Implementation
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> aux;
int i = 0, j = 0;
while(i < m and j < n) {
if(nums1[i] < nums2[j])
aux.push_back(nums1[i++]);
else
aux.push_back(nums2[j++]);
}
while(i < m)
aux.push_back(nums1[i++]);
while(j < n)
aux.push_back(nums2[j++]);
nums1 = aux;
}Time & Space Complexity
Space Complexity: O(N+M) [because the aux array will use space]
Time Complexity: O(N+M) [try to think on your own first]
Method 1 to understand Time Complexity
In each iteration of the 1st while loop, either i is incremented, or j is incremented.
This means that the number of times the 1st while loop runs will basically be equal to the value of i + j just after it ends. Now, we know that when it ends, either i will become equal to m or j will be n.
Let's say, i becomes equal to m, and j is equal to some random number k. That means the first while loop ran M + K times.
Now, let's analyse the 2nd and 3rd while loop. The 2nd loop will run 0 times because i is already equal to m. The 3rd while loop will run N - K times, as we assumed the value of j to be equal to K after the 1st while loop.
So, in total, no. of operations = (M + K) + (N - K).
Therefore, time complexity = O(N+M);
Method 1 (a crispier one)
Everytime any iteration is run, be it in while loop 1, 2 or 3, exactly 1 element is added to the auxiliary array.
We know that there are going to be exactly N + M elements in the aux array finally.
Therefore, time complexity = O(N + M)
Let's get rid of extra space as well
Please do read the above section before reading this one.
Here, we'll try to not use any auxiliary array, and put the merged elements in a sorted order directly to the arr1.
Hint 1
The problem is that we can't directly use arr1, because if we do so, then we'll end up overwriting the elements present in arr1, which will put is in a pickle.
But, what if instead of putting the elements from the start in increasing order, we put them from the end in decreasing order?
Hint 2
Instead of starting with i = 0 and j = 0 and incrementing them in each iteration, think of starting with i = m - 1 and j = n - 1, and decrementing them in each iteration.Hint 3
We may also need a 3rd pointer k, initialised with m + n - 1, where we'll put our elements finally.Complete explanation
As already explained in the hints above, we'll basically put the elements in decreasing order in arr1, and since there is empty space for N elements in the right of arr1, there is definitely not going to be a problem until then.
But what about the time when we've used up the empty space and we start overwriting the elements in arr1? We'll worry about that in a while, let's look at the complete approach first.
For this, we'll initialise 3 pointers: i = m - 1, j = n - 1 and k = n + m - 1, and start iterating while i >= 0 and j >= 0, doing the following in each iteration:
- If arr1[i] > arr2[j], then arr1[k] = arr1[i] and decrement the values of i & k by 1.
- Otherwise, then arr1[k] = arr2[j] and decrement the values of j & k by 1.
Now, after the above while loop ends, as explained in the above section as well, exactly 1 of the 2 arrays will have some un-resolved elements. In a manner similar to the above section, we'll simply add those elements appropriately.
Won't the overwriting be a problem?
The answer is no. The thing is that by the time we over-write a particular index k in arr1, the value of index i would've already become smaller than or equal to k, and that element arr1[k] would've already gone to its right place, making arr1[k] useless now. (1 specific case could be if i = k, here arr1[k] won't be useless, but it won't mess up the algorithm for sure)If you're really interested in understanding this thing, I urge you to take a few examples and try it yourself on pen and paper as this article has already reached almost 1500 words xD
Implementation
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = n + m - 1;
while(i >= 0 and j >= 0) {
if(nums1[i] > nums2[j])
nums1[k--] = nums1[i--];
else
nums1[k--] = nums2[j--];
}
while(i >= 0)
nums1[k--] = nums1[i--];
while(j >= 0)
nums1[k--] = nums2[j--];
}Time & Space Complexity
Space Complexity: O(1) [simply because no extra space is used xD]
Time Complexity: O(N+M) [please refer to the above section, it's explained in detail there]