1
00:00:00,600 --> 00:00:01,710
Welcome back.

2
00:00:01,710 --> 00:00:07,980
Now, before we start thinking about how we can solve this question, let's take a look at an interesting

3
00:00:07,980 --> 00:00:08,760
observation.

4
00:00:08,760 --> 00:00:11,940
Let's say the given array is 12345.

5
00:00:11,940 --> 00:00:13,650
And let's say k is equal to two.

6
00:00:13,650 --> 00:00:16,440
That is we're going to two two rotations to the right.

7
00:00:16,440 --> 00:00:22,200
So what happens first we get 51234 and then 45123.

8
00:00:22,200 --> 00:00:24,990
So this is how the array looks after two rotations.

9
00:00:24,990 --> 00:00:26,430
Now let's continue.

10
00:00:26,430 --> 00:00:28,560
And let's say k is equal to five.

11
00:00:28,560 --> 00:00:31,110
So at this point we have done two rotations.

12
00:00:31,110 --> 00:00:33,000
So we have to do three more rotations.

13
00:00:33,000 --> 00:00:33,210
So.

14
00:00:33,210 --> 00:00:34,500
So let's go ahead and do that.

15
00:00:34,500 --> 00:00:38,970
So we get 34512 and then 23451.

16
00:00:38,970 --> 00:00:41,160
So at this point we have done four rotations.

17
00:00:41,160 --> 00:00:44,070
Now we have to do one more rotation to get k is equal to five.

18
00:00:44,070 --> 00:00:45,240
So let's do that.

19
00:00:45,240 --> 00:00:48,840
So one comes over here and we get 12345.

20
00:00:48,840 --> 00:00:52,680
So notice that over here we started with 12345.

21
00:00:52,680 --> 00:00:57,030
And after five rotations we are back at 12345.

22
00:00:57,030 --> 00:00:58,680
All right now let's proceed.

23
00:00:58,680 --> 00:01:00,570
Let's say k is equal to seven.

24
00:01:00,570 --> 00:01:03,120
Now we have done already five rotations right.

25
00:01:03,120 --> 00:01:05,490
So this is 1234 and five.

26
00:01:05,490 --> 00:01:07,320
So we have to do two more rotations.

27
00:01:07,320 --> 00:01:08,460
So let's do that.

28
00:01:08,460 --> 00:01:14,370
So five comes over here we get 51234 and then 45123.

29
00:01:14,370 --> 00:01:15,960
So we have done seven rotations.

30
00:01:16,500 --> 00:01:16,980
All right.

31
00:01:16,980 --> 00:01:21,810
Now notice that when k is equal to two we got 45123.

32
00:01:21,810 --> 00:01:23,370
And when k is equal to seven.

33
00:01:23,370 --> 00:01:25,710
Also we got 45123.

34
00:01:25,710 --> 00:01:27,210
So these two are equal.

35
00:01:27,210 --> 00:01:28,500
Now why is that so right.

36
00:01:28,500 --> 00:01:31,920
So let's try to think about the logic behind this.

37
00:01:31,920 --> 00:01:35,880
Now seven is nothing but five into one plus two right.

38
00:01:35,880 --> 00:01:38,460
So seven is equal to five into one plus two.

39
00:01:38,460 --> 00:01:45,810
And we saw that the the array at two rotations and seven rotations was looking the same.

40
00:01:45,810 --> 00:01:51,690
Now we also saw that when k is equal to five we got back the initial array which is what we had over

41
00:01:51,690 --> 00:01:51,990
here.

42
00:01:51,990 --> 00:01:53,520
So why is this.

43
00:01:53,550 --> 00:01:58,470
Why is this so over here we can see that the length of this array is equal to five.

44
00:01:58,950 --> 00:01:59,400
All right.

45
00:01:59,400 --> 00:02:06,750
So after k number of rotations where k is equal to the length of the array we will get back the initial

46
00:02:06,750 --> 00:02:06,990
array.

47
00:02:06,990 --> 00:02:08,700
So over here the length is five.

48
00:02:08,700 --> 00:02:12,390
So after five rotations we are getting back the initial array.

49
00:02:12,390 --> 00:02:18,030
If the length of the array was ten then after ten rotations we would get back the initial array.

50
00:02:18,030 --> 00:02:18,600
All right.

51
00:02:18,600 --> 00:02:25,290
So over here if we want to find out how the array will look after seven rotations, we actually don't

52
00:02:25,290 --> 00:02:26,640
need to do seven rotations.

53
00:02:26,640 --> 00:02:30,060
We can take out all the multiples of five from seven.

54
00:02:30,060 --> 00:02:33,300
In this case we just have one multiple and then the remainder.

55
00:02:33,300 --> 00:02:36,480
We just need to do the reminder number of rotations.

56
00:02:36,480 --> 00:02:37,860
Now this is very useful right.

57
00:02:37,860 --> 00:02:42,060
For example let's say in the question it's given that k is equal to 103.

58
00:02:42,060 --> 00:02:44,430
So we don't need to do 103 rotations.

59
00:02:44,430 --> 00:02:44,850
Right.

60
00:02:44,850 --> 00:02:51,090
And even if the length is five then we take out all the multiples of five from 103.

61
00:02:51,090 --> 00:02:51,450
Right.

62
00:02:51,450 --> 00:02:54,600
So and then we just need to look at the reminder for this.

63
00:02:54,630 --> 00:02:57,570
We just need to do 103 divided by five.

64
00:02:57,570 --> 00:02:59,220
And we find the reminder.

65
00:02:59,220 --> 00:03:01,680
So for this we can use the modulo operator.

66
00:03:01,680 --> 00:03:08,460
We can do 103 modulo five which will give us the remainder when we divide 103 by five which is equal

67
00:03:08,460 --> 00:03:08,970
to three.

68
00:03:08,970 --> 00:03:16,230
So if we want to do 103 rotations, we will get the same array as it would look after doing three rotations.

69
00:03:16,230 --> 00:03:19,290
So if k is 103 the array would look like this.

70
00:03:19,290 --> 00:03:19,470
Right.

71
00:03:19,470 --> 00:03:20,970
This is one, two and three.

72
00:03:20,970 --> 00:03:23,520
So this is how the array looks after three rotations.

73
00:03:23,520 --> 00:03:25,440
Now after 103 rotations.

74
00:03:25,440 --> 00:03:27,510
Also it would look the same way.

75
00:03:27,510 --> 00:03:30,150
All right so this is an interesting thing that we observed.

76
00:03:30,150 --> 00:03:33,450
Now let's go ahead and think about solving the question.

77
00:03:33,450 --> 00:03:39,060
How do we implement a function which will rotate the given array by k times to the right.

78
00:03:39,060 --> 00:03:41,970
Let's say again this is the given array 12345.

79
00:03:41,970 --> 00:03:45,000
Now first we discuss the brute force method okay.

80
00:03:45,450 --> 00:03:51,690
Now if k is equal to two or k is equal to 102, we have seen we have to only rotate it two times.

81
00:03:51,690 --> 00:03:56,070
Now after two rotations we have seen that the array would look like this right.

82
00:03:56,070 --> 00:03:57,150
So we have four five.

83
00:03:57,150 --> 00:03:58,380
And then we have 123.

84
00:03:58,380 --> 00:04:00,210
After one rotation five comes over here.

85
00:04:00,210 --> 00:04:02,730
And after the second rotation four comes over here.

86
00:04:02,730 --> 00:04:03,300
All right.

87
00:04:03,330 --> 00:04:09,030
Now you can notice that over here this four and five is what is coming over here which is in the beginning.

88
00:04:09,030 --> 00:04:09,360
Right.

89
00:04:09,360 --> 00:04:15,360
So the brute force method would be that if you want to do k rotations and in this case k is equal to

90
00:04:15,360 --> 00:04:18,600
two, we take k elements from the end right.

91
00:04:18,600 --> 00:04:19,770
In this case k is two.

92
00:04:19,800 --> 00:04:23,850
So we take two elements from the end and we store it into a temporary array.

93
00:04:23,850 --> 00:04:26,400
So we have four and five in a temporary array.

94
00:04:26,400 --> 00:04:33,090
Then over here in the remaining part of the array which is this part, we shift the elements by k elements

95
00:04:33,090 --> 00:04:33,990
to the right right.

96
00:04:33,990 --> 00:04:36,000
So in this case k is equal to two.

97
00:04:36,030 --> 00:04:39,750
So we shift these elements by two to the right right.

98
00:04:39,750 --> 00:04:43,830
So after doing this three will be shifted by two elements to the right.

99
00:04:43,830 --> 00:04:47,130
So whatever is over here will be put over here.

100
00:04:47,130 --> 00:04:47,310
Right.

101
00:04:47,310 --> 00:04:48,840
So this is two elements to the right.

102
00:04:48,840 --> 00:04:50,580
So this will be put over here.

103
00:04:50,580 --> 00:04:53,640
Two will be put over here and one will be put over here.

104
00:04:53,640 --> 00:04:53,970
Right.

105
00:04:53,970 --> 00:04:56,640
So after doing this the array will look like this.

106
00:04:56,640 --> 00:04:56,850
Right.

107
00:04:56,850 --> 00:04:58,950
We have one two and then 123.

108
00:04:58,950 --> 00:04:59,160
Right.

109
00:04:59,160 --> 00:05:00,120
So over here.

110
00:05:00,220 --> 00:05:01,990
We got three, right?

111
00:05:01,990 --> 00:05:02,860
This three came over here.

112
00:05:02,860 --> 00:05:04,090
That's why we have three over here.

113
00:05:04,090 --> 00:05:05,140
This two came over here.

114
00:05:05,140 --> 00:05:06,310
That's why we have two over here.

115
00:05:06,310 --> 00:05:07,900
And this one came over here.

116
00:05:07,900 --> 00:05:09,160
That's why we have one over here.

117
00:05:09,160 --> 00:05:10,600
And then we have this one and two.

118
00:05:10,600 --> 00:05:10,900
Right.

119
00:05:10,900 --> 00:05:13,090
So we are doing it only for these three elements.

120
00:05:13,090 --> 00:05:13,480
Right.

121
00:05:13,480 --> 00:05:16,840
So for these three elements now the array looks like this.

122
00:05:16,840 --> 00:05:18,550
Now the last step right.

123
00:05:18,550 --> 00:05:20,230
How is it different from the output.

124
00:05:20,230 --> 00:05:21,940
We don't need one and two over here.

125
00:05:21,940 --> 00:05:22,360
Right.

126
00:05:22,360 --> 00:05:24,250
In this part we need four and five.

127
00:05:24,250 --> 00:05:31,210
So we replace the first k elements with the temporary array which we have already stored and kept.

128
00:05:31,210 --> 00:05:31,510
Right.

129
00:05:31,510 --> 00:05:33,250
So this is the brute force solution.

130
00:05:33,250 --> 00:05:36,040
Now we will not code the brute force solution together.

131
00:05:36,040 --> 00:05:40,840
But let's quickly look at the code over here and see how it can be implemented.

132
00:05:40,840 --> 00:05:42,910
So I have a function rotate array.

133
00:05:42,910 --> 00:05:43,450
Right.

134
00:05:43,450 --> 00:05:46,780
And then we find k is equal to k modulo length right.

135
00:05:46,780 --> 00:05:48,760
So that's to do this part over here.

136
00:05:48,760 --> 00:05:51,040
And then we have a temporary array.

137
00:05:51,040 --> 00:05:55,300
And we use the slice operator and we pass in length minus k.

138
00:05:55,300 --> 00:05:58,480
So in this case length is five and k is equal to two.

139
00:05:58,510 --> 00:05:58,720
Right.

140
00:05:58,720 --> 00:06:01,990
So we are passing five minus two which is equal to three right.

141
00:06:01,990 --> 00:06:05,020
So this is 012 and three.

142
00:06:05,020 --> 00:06:06,580
And then we have for the indices.

143
00:06:06,580 --> 00:06:08,980
So we are passing index three at this point.

144
00:06:08,980 --> 00:06:11,530
So temp will have four and five.

145
00:06:11,530 --> 00:06:14,560
So we are storing four and five in this temp over here.

146
00:06:15,070 --> 00:06:20,260
And then we are going to loop through from I is equal to length minus k minus one which is this one

147
00:06:20,260 --> 00:06:20,560
over here.

148
00:06:20,560 --> 00:06:20,890
Right.

149
00:06:20,890 --> 00:06:22,510
So we are going to start over here.

150
00:06:22,510 --> 00:06:28,720
And then we are going to say array at I plus k which is over here I is 012 right.

151
00:06:28,720 --> 00:06:30,400
This is two and then k is two.

152
00:06:30,430 --> 00:06:33,280
So two plus two which is equal to this one over here.

153
00:06:33,280 --> 00:06:35,800
So over here we are going to have three at this point.

154
00:06:35,800 --> 00:06:36,220
Right.

155
00:06:36,220 --> 00:06:40,360
Similarly we are going to have two over here and one over here which is this second step.

156
00:06:40,360 --> 00:06:42,250
So we are doing the second step over here.

157
00:06:42,250 --> 00:06:44,740
And then finally we have the temp array.

158
00:06:44,860 --> 00:06:46,240
And we have this array.

159
00:06:46,240 --> 00:06:50,650
So we are going to say this for should this is index zero and this is index one.

160
00:06:50,650 --> 00:06:55,090
So index zero at the array should be what is at index zero in the temporary.

161
00:06:55,090 --> 00:06:56,260
So we get four over here.

162
00:06:56,260 --> 00:07:01,990
And index one in the array should be what we have at index one in the temp array.

163
00:07:01,990 --> 00:07:02,980
So we have five over here.

164
00:07:02,980 --> 00:07:04,120
That five comes over here.

165
00:07:04,120 --> 00:07:05,350
That is what we're doing over here.

166
00:07:05,350 --> 00:07:06,730
And then we just return the array.

167
00:07:06,730 --> 00:07:09,580
So this is our brute force solution right now.

168
00:07:09,580 --> 00:07:13,330
Let's quickly look at the time and space complexity of this solution.

169
00:07:13,330 --> 00:07:20,770
Now you can see that if the length of the array is equal to n, then between these two for loops we

170
00:07:20,770 --> 00:07:22,240
will do n operations.

171
00:07:22,600 --> 00:07:22,990
Right.

172
00:07:22,990 --> 00:07:26,470
So over here we are doing the operations for this part.

173
00:07:26,470 --> 00:07:26,800
Right.

174
00:07:26,800 --> 00:07:31,390
And then over here in the second for loop we are doing operations for equal to the length of the temporary.

175
00:07:31,390 --> 00:07:34,930
So you can see that the total number of operations will be n right.

176
00:07:34,930 --> 00:07:38,200
And again remember we are using the slice operator over here.

177
00:07:38,200 --> 00:07:42,700
And in this case the time complexity of the slice operator is n minus star.

178
00:07:42,730 --> 00:07:43,030
Right.

179
00:07:43,030 --> 00:07:48,070
So again over here we are doing o of k where k is the number of elements in the temp array.

180
00:07:48,070 --> 00:07:49,960
And again k will be less than n.

181
00:07:49,960 --> 00:07:55,060
So we can ignore this over here because we are all anyway doing n operations which is greater than k.

182
00:07:55,060 --> 00:07:57,940
And remember Big-O always gives us the upper bound.

183
00:07:57,940 --> 00:08:05,050
So we can say that the time complexity is n plus k, and because k is less than n, it converges to

184
00:08:05,050 --> 00:08:08,680
o of n, so time complexity is equal to o of n.

185
00:08:08,680 --> 00:08:10,750
Now what about the space complexity?

186
00:08:10,750 --> 00:08:12,640
We are using a temp array over here.

187
00:08:12,640 --> 00:08:12,850
Right.

188
00:08:12,850 --> 00:08:16,030
We are using this which is auxiliary space right.

189
00:08:16,030 --> 00:08:19,270
That's extra space because we are having this temporary array.

190
00:08:19,270 --> 00:08:23,890
And that's why we can say that the space complexity of this solution is O of k.

191
00:08:23,980 --> 00:08:24,550
All right.

192
00:08:24,550 --> 00:08:26,440
So this is the brute force method.

193
00:08:26,440 --> 00:08:32,350
Now let's look at it at a better method which will again have O of n time complexity.

194
00:08:32,350 --> 00:08:34,840
But we will have a better space complexity.

195
00:08:34,840 --> 00:08:36,850
So let's look at the second method.

196
00:08:37,360 --> 00:08:37,720
All right.

197
00:08:37,720 --> 00:08:39,430
So this is a trick for this question.

198
00:08:39,430 --> 00:08:43,630
Now let's say the given array is 12345 and six.

199
00:08:43,630 --> 00:08:45,340
And let's say k is equal to two.

200
00:08:45,370 --> 00:08:48,250
So we know that six comes over here after one rotation.

201
00:08:48,250 --> 00:08:51,400
And then five also will join over here after the second rotation.

202
00:08:51,400 --> 00:08:55,840
So the output which is required will be 56123 and four.

203
00:08:55,840 --> 00:08:56,320
All right.

204
00:08:56,320 --> 00:09:02,760
Now let's just reverse this array 123456 and make some observations.

205
00:09:02,760 --> 00:09:07,410
So after reversing this array we will get 65432 and one.

206
00:09:07,410 --> 00:09:07,740
Right.

207
00:09:07,740 --> 00:09:10,320
So we have just reversed the given array.

208
00:09:10,320 --> 00:09:17,580
And then if we compare the reversed array over here and the final output which we require, you can

209
00:09:17,580 --> 00:09:20,640
see that this part over here is just the reverse right.

210
00:09:20,640 --> 00:09:23,670
So if we just reverse this we will get five and six over here.

211
00:09:23,670 --> 00:09:29,130
Similarly this part over here, if we just reverse this we will get one, two three, four over here

212
00:09:29,130 --> 00:09:31,140
which is the output which we require.

213
00:09:31,140 --> 00:09:31,440
Right.

214
00:09:31,440 --> 00:09:36,450
So from this observation we can build a solution for this question.

215
00:09:36,450 --> 00:09:41,490
So first we are going to do this part over here which is we are just going to reverse the array which

216
00:09:41,490 --> 00:09:42,420
is given to us.

217
00:09:42,420 --> 00:09:44,910
And let me just write the indices over here.

218
00:09:45,360 --> 00:09:48,690
If k is equal to two we can see that over here we have zero.

219
00:09:48,690 --> 00:09:49,800
And then we have one right.

220
00:09:49,800 --> 00:09:51,300
So this is nothing but zero.

221
00:09:51,330 --> 00:09:52,350
This will be still zero.

222
00:09:52,350 --> 00:09:55,380
But this will have elements up to k minus one.

223
00:09:55,380 --> 00:09:55,560
Right.

224
00:09:55,560 --> 00:09:57,150
So this will be k minus one.

225
00:09:57,150 --> 00:09:58,560
Just making it generic.

226
00:09:58,560 --> 00:10:00,000
And then this would be the next.

227
00:10:00,220 --> 00:10:02,200
Element, which is k right index k.

228
00:10:02,200 --> 00:10:05,230
And then the last index over here is length minus one.

229
00:10:05,230 --> 00:10:09,220
So again now all we have to do is we have to reverse these two right.

230
00:10:09,220 --> 00:10:10,570
We have to just reverse these two.

231
00:10:10,570 --> 00:10:13,180
And we have to reverse this part of the array.

232
00:10:13,180 --> 00:10:15,820
So when we reverse this we'll get five and six over here.

233
00:10:15,820 --> 00:10:20,350
And when we reverse the elements in this part of the array we will get 1234 over here.

234
00:10:20,350 --> 00:10:21,820
So that is the second step.

235
00:10:21,820 --> 00:10:27,610
So reverse the elements from zero to k minus one which is this part, and reverse the elements from

236
00:10:27,610 --> 00:10:29,380
k to length minus one.

237
00:10:29,380 --> 00:10:31,390
And that will give us the solution.

238
00:10:31,390 --> 00:10:36,610
Right now this is a better solution because you can see that we are not making use of any auxiliary

239
00:10:36,610 --> 00:10:37,060
space.

240
00:10:37,060 --> 00:10:42,130
So the space complexity of this solution will be O of one or constant space.

241
00:10:42,130 --> 00:10:44,080
Now what about the time complexity?

242
00:10:44,080 --> 00:10:47,710
The time complexity of this solution is still O of n.

243
00:10:47,710 --> 00:10:50,740
Now you can see that we are doing one reversal over here, right?

244
00:10:50,740 --> 00:10:54,340
So reversing a given array is an O of n operation.

245
00:10:54,340 --> 00:10:54,730
Right.

246
00:10:54,730 --> 00:10:56,890
So we are just going to have two pointers.

247
00:10:56,890 --> 00:10:58,750
And it will be at the beginning and the end.

248
00:10:58,750 --> 00:11:04,120
And then we'll keep swapping the values as long as the let's say this is the start pointer and this

249
00:11:04,120 --> 00:11:04,900
is the end pointer.

250
00:11:04,900 --> 00:11:05,170
Right.

251
00:11:05,170 --> 00:11:11,860
So we are going to reverse the this swap the values at start and end as long as start is less than n.

252
00:11:11,860 --> 00:11:13,690
So that's how we reverse the array.

253
00:11:13,690 --> 00:11:19,720
So this is an O of n operation right now strictly you could say it's something like o of n by two.

254
00:11:19,720 --> 00:11:22,660
But then that one by two is just a constant.

255
00:11:22,660 --> 00:11:22,840
Right.

256
00:11:22,840 --> 00:11:24,760
So this is an O of n operation.

257
00:11:24,760 --> 00:11:26,470
The first step over here.

258
00:11:26,470 --> 00:11:29,560
And then we are going to reverse these this part and this part over here.

259
00:11:29,560 --> 00:11:29,950
Right.

260
00:11:29,950 --> 00:11:33,760
Again these two together is going to be an O of n operation.

261
00:11:33,760 --> 00:11:38,170
So together n plus N2N again two is a constant.

262
00:11:38,170 --> 00:11:39,010
We can avoid it.

263
00:11:39,010 --> 00:11:43,420
That's why we can say that the time complexity of this solution is still o of n.

264
00:11:43,420 --> 00:11:47,650
But over here we made an improvement over the brute force method which we discussed previously.

265
00:11:47,650 --> 00:11:52,990
There we had to have a auxiliary space used right because we had a temporary array.

266
00:11:52,990 --> 00:11:56,170
But this, this method over here runs in constant space.

267
00:11:56,170 --> 00:11:58,780
That is, the space complexity is O of one.