In the previous video, we saw how we could solve this problem with the time complexity of O of n log
n and space complexity of O of n.
Now anyway, we have to form a new array, so we cannot improve on the space complexity.
But let's try to improve the time complexity, which is o of n log n as per the brute force method.
Now notice that in the previous method, we did not use the fact that the input array was sorted.
Right.
Now let's try to make use of that fact and improve the time complexity.
All right.
So we're going to try to use the fact that the given array is sorted in ascending order.
So let's look at it now.
Now again we have an example minus three one two and seven.
Now first let's make a new array and initialize uh, all of the indices of the new array to zero.
And let the length of the new array be the same as the length of the initially given array.
All right.
So we have done that now.
Now let's look at a property of numbers.
Over here we have the number line.
And notice that as you go towards the left and the right from zero the value of squares keeps increasing
right.
For example let's say that you have one over here, you have two over here and you have ten over here.
So as we go from zero towards the right, the square is one 400, etc..
So it's increasing and the same is observed when you go towards the left also.
Right.
So you have minus one.
Let's say you have minus three and let's say you have minus nine.
So as you see as you go to the extremes the square value increases.
Right.
So the same has to be true when we look at the sorted array which is given to us right now, we are
more likely to find the greater value as we go to the two extremes of the given array.
Now why do I say that we are more likely?
It could be that our array is just one, two, five and ten.
This also is a sorted array.
Now over here you can see that we are only part of this part of the number line.
So as we go towards the right the squares increase right.
But then we could also have an array which is like minus nine, minus eight, one and two.
Right.
So over here we can see that we have moved more towards the left from zero in this part.
So the square would be higher here rather than here.
So this is an interesting property.
So let's try to make use of this property to solve this in a better manner.
Now because this is true if we look at the two extreme positions of the given array which is this position
and this position, and if we square them, then one among these two definitely has to be the greatest
or right, the greatest square.
Now why is that?
So now if we have a value over here and let's say we have a negative, I have minus three and I have
minus two.
So definitely minus three square will be greater than minus two square.
So yes this is true.
And again over here also if I have two and three three square is greater than two.
So we are just looking at which is the greatest positive value or the greatest negative value.
Right.
So we just need to look at these two extremes.
And we can be sure that one among these two will be the greatest when we square it.
Right.
So let's make use of this property to solve this question in a more time efficient manner.
Right.
So one among these two has to be the largest.
When we square all these four, the largest has to be one among the squares of these two.
Right.
It will definitely not be one among the squares of these two.
Right.
All right.
So let's look at that.
Three square is nine and seven square is 49.
So nine is less than 49 or the greater value is 49.
So let's take this 49 and we fill this 49 over here.
That is the new array.
This is the new array which we made.
And let's fill this 49 at the last position of the new array which is over here.
So we write 49 over here.
Now we got this 49 by doing seven square right.
So we have already used this up.
So let's move the pointer from here one to to the left which is two two.
All right.
So again our pointer one pointer is over here and one pointer is over here.
Now the next greatest or the next largest.
When we square these three has to be one among the squares of these two.
Right.
So let's look at that.
Minus three square gives us nine and two square gives us four.
Now nine is greater than four.
So let's fill the next position in the new array which is this one.
Over here.
Let's fill the new position with nine.
So we put nine over here.
And we got nine by squaring minus three.
So we have already used it up.
And hence let's move this pointer one towards the right.
Right.
So we move the pointer over here.
Now the two pointers are at one and two.
Now again the next largest has to be one among the squares of these two.
So again when we square we get one and four one is less than four.
So we fill four over here which is at the next position in the array, the new array which we are creating.
And we are just left with one.
And the two pointers at this point, point at the same value.
And we fill that over here, which is one right now we can see that we have got the array and it is
sorted.
We got 149 49.
So this is the array.
And it consists of the sorted integers of the given array.
And this array over here is also sorted.
So this is the better optimized solution or the better approach by which we can solve this problem.
Again remember the property which we used is that the greatest when we square all the input like let's
say we have an input array like minus ten of minus three, five, nine, 11, 12.
So even irrespective of what the values are given in the array, the greatest when we square all of
these will be one among minus ten square and 12 square, right.
So we just need to compare these two, find the greatest and fill it at the last position of the new
array.
And then whichever was used up shift the pointer accordingly and keep comparing those two values and
find the next one.
In this way we filled the largest value at the rightmost most position, the second largest value at
the next position.
And we kept repeating that, and we got the sorted array, where each element was the square of the
given elements in the initial array.
All right.
Now let's look at the space and time complexity of this approach.
Initial approach.
We have seen as per the brute force solution, the time complexity was n log n and the space complexity
was O of n.
Right now let's look at the space and time complexity of this solution.
Over here we can see that we are only traversing the array once right?
So the time complexity is only O of n.
Now this is because we are just moving or traversing the array one time right now.
What about the space complexity?
The space complexity is still O of N because we are making a new array, which is this array over here.
Now we can see that by using this property and the fact that the input array was already sorted, we
were able to optimize the solution.
And instead of O of n log n, we got a solution with the time complexity of O of n.