Hi everyone, I hope you have thought about how to solve this on your own.
Now let's look at how to solve this together.
The first method is the brute force method.
All right so let's look at this method over here.
For this let's take a sample input.
Let's say the input is minus three one two and seven.
So we have this array as input.
Notice that this is sorted.
All right.
Now the brute force method is that we just square each element and put it in a new array.
Right.
So that uh after doing that what would be the array.
The array would be 914 and 49.
Right.
We are just squaring each element and putting it in a new array.
So minus three square is nine, one square is one, two square is four and seven square is 49.
Now notice that this array over here is not sorted now.
So the next step would be that we have to sort this array.
And once we sort this array we will get the required output which is 149 and 49.
Now this is very simple but it does not have the best space and time complexity.
Now let's look at the space and time complexity of this solution.
Now over here notice that we have traversed the array.
And we have squared each element and put it in a new array.
Right.
So we have traversed it one time.
Let's say this array has n elements.
So the time complexity of this operation is O of n right.
We are just traversing it one time.
Now after this we have to sort right.
We have to sort the given array to get from here to here right now.
Any good sort is has a time complexity of o of n log n for example, quicksort, etc..
Right.
So the total time complexity of this algorithm therefore is equal to o of n log n.
Now you could say that it is O of n log n plus n right o of n log n plus n.
Yes, we can say that.
But again this simplifies to n log n.
Why is that so?
Because n log n is greater than n right in.
In the logarithm section we have seen that already n log n is greater than n.
Now if n log n is greater than n, you can either just remove this and you're just left with n log n,
or you can think of it in this way instead of n, let's replace it with n log n.
So when we add these two, we get two n log n.
And then this is a constant.
So we can remove the constant.
And again we are getting n log n.
So the time complexity of the brute force method is n log n.
Now what about the space complexity of this solution over here?
Notice that we have made a new array with n elements.
So we have consumed some space.
Therefore the space complexity of this algorithm is O of n right.
This will have n elements.
If the input array has n elements, the new array also will have n elements.
So the space complexity is O of n.
All right.
So we have seen that the time complexity is O of n log n and the space complexity is O of n.
Now this is the brute force method.
We will see in the next video how we can do better than this.