Welcome back.
Now, before we start thinking about how we can solve this question, let's take a look at an interesting
observation.
Let's say the given array is 12345.
And let's say k is equal to two.
That is we're going to two two rotations to the right.
So what happens first we get 51234 and then 45123.
So this is how the array looks after two rotations.
Now let's continue.
And let's say k is equal to five.
So at this point we have done two rotations.
So we have to do three more rotations.
So.
So let's go ahead and do that.
So we get 34512 and then 23451.
So at this point we have done four rotations.
Now we have to do one more rotation to get k is equal to five.
So let's do that.
So one comes over here and we get 12345.
So notice that over here we started with 12345.
And after five rotations we are back at 12345.
All right now let's proceed.
Let's say k is equal to seven.
Now we have done already five rotations right.
So this is 1234 and five.
So we have to do two more rotations.
So let's do that.
So five comes over here we get 51234 and then 45123.
So we have done seven rotations.
All right.
Now notice that when k is equal to two we got 45123.
And when k is equal to seven.
Also we got 45123.
So these two are equal.
Now why is that so right.
So let's try to think about the logic behind this.
Now seven is nothing but five into one plus two right.
So seven is equal to five into one plus two.
And we saw that the the array at two rotations and seven rotations was looking the same.
Now we also saw that when k is equal to five we got back the initial array which is what we had over
here.
So why is this.
Why is this so over here we can see that the length of this array is equal to five.
All right.
So after k number of rotations where k is equal to the length of the array we will get back the initial
array.
So over here the length is five.
So after five rotations we are getting back the initial array.
If the length of the array was ten then after ten rotations we would get back the initial array.
All right.
So over here if we want to find out how the array will look after seven rotations, we actually don't
need to do seven rotations.
We can take out all the multiples of five from seven.
In this case we just have one multiple and then the remainder.
We just need to do the reminder number of rotations.
Now this is very useful right.
For example let's say in the question it's given that k is equal to 103.
So we don't need to do 103 rotations.
Right.
And even if the length is five then we take out all the multiples of five from 103.
Right.
So and then we just need to look at the reminder for this.
We just need to do 103 divided by five.
And we find the reminder.
So for this we can use the modulo operator.
We can do 103 modulo five which will give us the remainder when we divide 103 by five which is equal
to three.
So if we want to do 103 rotations, we will get the same array as it would look after doing three rotations.
So if k is 103 the array would look like this.
Right.
This is one, two and three.
So this is how the array looks after three rotations.
Now after 103 rotations.
Also it would look the same way.
All right so this is an interesting thing that we observed.
Now let's go ahead and think about solving the question.
How do we implement a function which will rotate the given array by k times to the right.
Let's say again this is the given array 12345.
Now first we discuss the brute force method okay.
Now if k is equal to two or k is equal to 102, we have seen we have to only rotate it two times.
Now after two rotations we have seen that the array would look like this right.
So we have four five.
And then we have 123.
After one rotation five comes over here.
And after the second rotation four comes over here.
All right.
Now you can notice that over here this four and five is what is coming over here which is in the beginning.
Right.
So the brute force method would be that if you want to do k rotations and in this case k is equal to
two, we take k elements from the end right.
In this case k is two.
So we take two elements from the end and we store it into a temporary array.
So we have four and five in a temporary array.
Then over here in the remaining part of the array which is this part, we shift the elements by k elements
to the right right.
So in this case k is equal to two.
So we shift these elements by two to the right right.
So after doing this three will be shifted by two elements to the right.
So whatever is over here will be put over here.
Right.
So this is two elements to the right.
So this will be put over here.
Two will be put over here and one will be put over here.
Right.
So after doing this the array will look like this.
Right.
We have one two and then 123.
Right.
So over here.
We got three, right?
This three came over here.
That's why we have three over here.
This two came over here.
That's why we have two over here.
And this one came over here.
That's why we have one over here.
And then we have this one and two.
Right.
So we are doing it only for these three elements.
Right.
So for these three elements now the array looks like this.
Now the last step right.
How is it different from the output.
We don't need one and two over here.
Right.
In this part we need four and five.
So we replace the first k elements with the temporary array which we have already stored and kept.
Right.
So this is the brute force solution.
Now we will not code the brute force solution together.
But let's quickly look at the code over here and see how it can be implemented.
So I have a function rotate array.
Right.
And then we find k is equal to k modulo length right.
So that's to do this part over here.
And then we have a temporary array.
And we use the slice operator and we pass in length minus k.
So in this case length is five and k is equal to two.
Right.
So we are passing five minus two which is equal to three right.
So this is 012 and three.
And then we have for the indices.
So we are passing index three at this point.
So temp will have four and five.
So we are storing four and five in this temp over here.
And then we are going to loop through from I is equal to length minus k minus one which is this one
over here.
Right.
So we are going to start over here.
And then we are going to say array at I plus k which is over here I is 012 right.
This is two and then k is two.
So two plus two which is equal to this one over here.
So over here we are going to have three at this point.
Right.
Similarly we are going to have two over here and one over here which is this second step.
So we are doing the second step over here.
And then finally we have the temp array.
And we have this array.
So we are going to say this for should this is index zero and this is index one.
So index zero at the array should be what is at index zero in the temporary.
So we get four over here.
And index one in the array should be what we have at index one in the temp array.
So we have five over here.
That five comes over here.
That is what we're doing over here.
And then we just return the array.
So this is our brute force solution right now.
Let's quickly look at the time and space complexity of this solution.
Now you can see that if the length of the array is equal to n, then between these two for loops we
will do n operations.
Right.
So over here we are doing the operations for this part.
Right.
And then over here in the second for loop we are doing operations for equal to the length of the temporary.
So you can see that the total number of operations will be n right.
And again remember we are using the slice operator over here.
And in this case the time complexity of the slice operator is n minus star.
Right.
So again over here we are doing o of k where k is the number of elements in the temp array.
And again k will be less than n.
So we can ignore this over here because we are all anyway doing n operations which is greater than k.
And remember Big-O always gives us the upper bound.
So we can say that the time complexity is n plus k, and because k is less than n, it converges to
o of n, so time complexity is equal to o of n.
Now what about the space complexity?
We are using a temp array over here.
Right.
We are using this which is auxiliary space right.
That's extra space because we are having this temporary array.
And that's why we can say that the space complexity of this solution is O of k.
All right.
So this is the brute force method.
Now let's look at it at a better method which will again have O of n time complexity.
But we will have a better space complexity.
So let's look at the second method.
All right.
So this is a trick for this question.
Now let's say the given array is 12345 and six.
And let's say k is equal to two.
So we know that six comes over here after one rotation.
And then five also will join over here after the second rotation.
So the output which is required will be 56123 and four.
All right.
Now let's just reverse this array 123456 and make some observations.
So after reversing this array we will get 65432 and one.
Right.
So we have just reversed the given array.
And then if we compare the reversed array over here and the final output which we require, you can
see that this part over here is just the reverse right.
So if we just reverse this we will get five and six over here.
Similarly this part over here, if we just reverse this we will get one, two three, four over here
which is the output which we require.
Right.
So from this observation we can build a solution for this question.
So first we are going to do this part over here which is we are just going to reverse the array which
is given to us.
And let me just write the indices over here.
If k is equal to two we can see that over here we have zero.
And then we have one right.
So this is nothing but zero.
This will be still zero.
But this will have elements up to k minus one.
Right.
So this will be k minus one.
Just making it generic.
And then this would be the next.
Element, which is k right index k.
And then the last index over here is length minus one.
So again now all we have to do is we have to reverse these two right.
We have to just reverse these two.
And we have to reverse this part of the array.
So when we reverse this we'll get five and six over here.
And when we reverse the elements in this part of the array we will get 1234 over here.
So that is the second step.
So reverse the elements from zero to k minus one which is this part, and reverse the elements from
k to length minus one.
And that will give us the solution.
Right now this is a better solution because you can see that we are not making use of any auxiliary
space.
So the space complexity of this solution will be O of one or constant space.
Now what about the time complexity?
The time complexity of this solution is still O of n.
Now you can see that we are doing one reversal over here, right?
So reversing a given array is an O of n operation.
Right.
So we are just going to have two pointers.
And it will be at the beginning and the end.
And then we'll keep swapping the values as long as the let's say this is the start pointer and this
is the end pointer.
Right.
So we are going to reverse the this swap the values at start and end as long as start is less than n.
So that's how we reverse the array.
So this is an O of n operation right now strictly you could say it's something like o of n by two.
But then that one by two is just a constant.
Right.
So this is an O of n operation.
The first step over here.
And then we are going to reverse these this part and this part over here.
Right.
Again these two together is going to be an O of n operation.
So together n plus N2N again two is a constant.
We can avoid it.
That's why we can say that the time complexity of this solution is still o of n.
But over here we made an improvement over the brute force method which we discussed previously.
There we had to have a auxiliary space used right because we had a temporary array.
But this, this method over here runs in constant space.
That is, the space complexity is O of one.