1
00:00:01,140 --> 00:00:01,870
Hi, everyone.

2
00:00:01,890 --> 00:00:09,450
So today in this video, we are going to solve this question, find a minimum element in our sorted

3
00:00:09,450 --> 00:00:09,770
Eddie.

4
00:00:10,650 --> 00:00:13,000
OK, so consider this example.

5
00:00:13,020 --> 00:00:15,330
So this is sorted, Eddie.

6
00:00:15,690 --> 00:00:17,250
And what is the minimum element?

7
00:00:17,260 --> 00:00:18,870
So the minimum element is one.

8
00:00:18,870 --> 00:00:20,960
So our output will be one.

9
00:00:22,020 --> 00:00:23,230
Consider this example.

10
00:00:23,520 --> 00:00:28,530
So this is our attitude sorted, Eddie, and we have to find the minimum element.

11
00:00:28,720 --> 00:00:34,620
OK, so in this example, zero is the minimum element, so our output will be zero.

12
00:00:35,550 --> 00:00:40,560
OK, so this is our question and assumption is basically.

13
00:00:41,610 --> 00:00:43,220
There are no duplicates element.

14
00:00:43,280 --> 00:00:46,110
OK, so assumption is not obligated elements, are there?

15
00:00:49,160 --> 00:00:52,200
So I have to find the minimum element.

16
00:00:52,820 --> 00:00:55,390
Now let us discuss how we can solve this question.

17
00:00:55,700 --> 00:01:02,690
Now, the first approach, the brute force approach is basically with the help of linear search.

18
00:01:03,470 --> 00:01:09,470
OK, what we will do, we will simply iterate over there and we will find out the minimum element.

19
00:01:09,950 --> 00:01:16,520
OK, so what will be the time and the space complexities all the time will be well and the space will

20
00:01:16,520 --> 00:01:17,120
be open.

21
00:01:17,360 --> 00:01:25,070
OK, but since the search is not considering the fact that given that it is basically a today, I rotated

22
00:01:25,070 --> 00:01:25,640
sorted out.

23
00:01:26,260 --> 00:01:30,260
OK, so we will solve this question with the help of binary search.

24
00:01:31,670 --> 00:01:34,830
OK, we will solve this question with the help of Minnesota.

25
00:01:34,850 --> 00:01:38,450
Now let's see how Minnesota search will help us to solve this question.

26
00:01:39,140 --> 00:01:39,500
OK.

27
00:01:41,360 --> 00:01:44,690
So since the days are rotated, sorted out and.

28
00:01:45,670 --> 00:01:52,750
The result today is the graph of the disorder that is very simple, so it will look something like this.

29
00:01:53,680 --> 00:01:59,620
There are no duplicates, so it will continue to increase and then there will be a sudden drop.

30
00:01:59,890 --> 00:02:02,650
OK, so there will be a sudden drop.

31
00:02:02,650 --> 00:02:07,510
And again, the elements are continuously increasing because there are no duplicates.

32
00:02:07,540 --> 00:02:14,500
OK, so this is New Start Point and this is the end point of the day and we have to find the minimum

33
00:02:14,500 --> 00:02:15,050
element.

34
00:02:15,340 --> 00:02:18,170
So this is basically the minimum element.

35
00:02:18,190 --> 00:02:23,080
OK, we have to find at this point, this is basically the minimum element.

36
00:02:24,320 --> 00:02:30,290
OK, so we have already sold similar kind of question, so again, first of all, what we will do,

37
00:02:30,300 --> 00:02:31,140
we will find out.

38
00:02:31,650 --> 00:02:35,960
OK, so we will find out which will be a start plus.

39
00:02:35,960 --> 00:02:36,770
And why do.

40
00:02:37,760 --> 00:02:39,380
OK, so Gayson.

41
00:02:40,570 --> 00:02:47,590
So for this, the first case, so after finding out the MD, what I will do, so basically this is the

42
00:02:47,590 --> 00:02:48,360
minimum element.

43
00:02:48,610 --> 00:02:54,450
So the next element, this is the next element and this is the previous element.

44
00:02:54,850 --> 00:03:01,350
So both the next and the previous element are greater than the minimum element, obviously.

45
00:03:01,570 --> 00:03:07,930
So after finding out the element, what I will do so the small element should be smaller then the next

46
00:03:07,930 --> 00:03:14,520
element and this element should be smaller than the previous element.

47
00:03:15,070 --> 00:03:19,800
If this is the case, then we have to find then we have already found out our minimum element.

48
00:03:19,810 --> 00:03:25,360
So I will return it because it is the smallest element, so I will return.

49
00:03:26,290 --> 00:03:28,840
OK, so this is very simple example.

50
00:03:28,840 --> 00:03:29,710
Very simple case.

51
00:03:29,740 --> 00:03:32,320
OK, now the second case.

52
00:03:33,550 --> 00:03:35,350
Second guess is this is not true.

53
00:03:35,530 --> 00:03:37,130
OK, so this is not true.

54
00:03:37,150 --> 00:03:39,080
Now I have to find out where my lies.

55
00:03:39,580 --> 00:03:41,740
So suppose it lies here.

56
00:03:42,010 --> 00:03:44,390
OK, what is the condition for me to lie here?

57
00:03:45,100 --> 00:03:50,120
So basically made will be less than and less than articles close to end.

58
00:03:50,200 --> 00:03:52,070
OK, so is lying here.

59
00:03:52,210 --> 00:03:59,530
Now what we have to do if mom is lying here, then we know that the smallest point will be in the left

60
00:03:59,530 --> 00:04:00,050
hand side.

61
00:04:00,280 --> 00:04:01,990
So what I will I will do.

62
00:04:01,990 --> 00:04:04,240
So I will do and equals minus one.

63
00:04:05,970 --> 00:04:13,800
OK, now let us consider turkeys, so in the third turkeys is lying here, OK, so it is lying here.

64
00:04:13,950 --> 00:04:14,640
Is a condition.

65
00:04:14,640 --> 00:04:16,910
So it is basically good.

66
00:04:16,920 --> 00:04:17,579
Then start.

67
00:04:17,730 --> 00:04:19,440
OK, so it is good.

68
00:04:19,470 --> 00:04:26,730
Then start now from the diagram we can see the minimum element will lie in the right hand side.

69
00:04:26,870 --> 00:04:32,250
OK, so what I will do, I will do start equals mid plus one.

70
00:04:33,260 --> 00:04:35,420
OK, so this is very simple.

71
00:04:35,720 --> 00:04:39,550
OK, we have to these three conditions are very, very simple, OK?

72
00:04:39,800 --> 00:04:43,900
Find out the method compared with the next element and the previous element.

73
00:04:43,910 --> 00:04:48,030
Obviously, this has to be the smallest element, which we are going to find out the minimum element.

74
00:04:48,350 --> 00:04:51,670
So if this condition is true, I will simply return it.

75
00:04:51,920 --> 00:04:56,050
If this condition is not true, try to find out where it is laying.

76
00:04:56,060 --> 00:04:58,850
If it lays here, then go in the left hand side.

77
00:04:59,120 --> 00:05:02,430
If my life is here, then go in the right hand side, OK?

78
00:05:02,510 --> 00:05:03,820
So these are the conditions.

79
00:05:04,400 --> 00:05:07,390
So this question is basically present only at court.

80
00:05:07,670 --> 00:05:09,620
And now let us write the cold.

81
00:05:09,620 --> 00:05:11,840
OK, so cold is going to be very, very simple.

82
00:05:13,010 --> 00:05:18,180
OK, so let us see how we can find out the next and the previous.

83
00:05:18,440 --> 00:05:19,600
So what will be next.

84
00:05:20,270 --> 00:05:23,770
So next will we basically made a plus one.

85
00:05:24,320 --> 00:05:26,500
OK, and what is previous.

86
00:05:26,660 --> 00:05:28,810
So previous is basically a minus one.

87
00:05:29,270 --> 00:05:33,060
OK, very simple but there is no confusion here.

88
00:05:33,080 --> 00:05:36,430
OK, so suppose if the value of is end ok.

89
00:05:36,680 --> 00:05:42,200
Suppose if it is basically close to end then what they are doing are trying to find out next.

90
00:05:42,230 --> 00:05:43,040
So what is next.

91
00:05:44,060 --> 00:05:50,790
So next will become and plus one and obviously this is Eddie and the plus one next.

92
00:05:50,810 --> 00:05:54,440
So this index does not exist so you will get married.

93
00:05:55,920 --> 00:06:02,070
You will get around demora now to avoid the entire matter, what I will do so let's say the size of

94
00:06:02,070 --> 00:06:08,630
the error is an OK, so you will you will have to write more than OK.

95
00:06:08,820 --> 00:06:10,950
So and plus one.

96
00:06:12,070 --> 00:06:17,220
Martin, so this is basically and I think this is and normally so and more than this will become zero.

97
00:06:17,230 --> 00:06:19,360
So I will likely reach here.

98
00:06:21,230 --> 00:06:26,570
OK, and similarly with the previous, so you are dealing with a minus one, I suppose, maydays zero,

99
00:06:26,750 --> 00:06:30,440
so zero minus one does not exist, basically minus one does not exist.

100
00:06:30,740 --> 00:06:35,140
So for handling this case, what we have to do, you have to add plus and first.

101
00:06:35,720 --> 00:06:40,290
OK, so minus one plus N what will happen, you will reach an endpoint.

102
00:06:41,230 --> 00:06:43,520
OK, and obviously you have to do more than.

103
00:06:45,220 --> 00:06:52,000
OK, so we are basically jumping so modern, basically, it will help us jump from here to here and

104
00:06:52,000 --> 00:06:53,500
obviously from here to here.

105
00:06:54,610 --> 00:06:57,190
OK, so let me write the code and I will explain it again.

106
00:06:58,370 --> 00:06:59,960
So our goal is very simple.

107
00:07:01,740 --> 00:07:09,600
First, let us change the name to be at a OK, so I have to find the minimum element, so start zero.

108
00:07:11,170 --> 00:07:14,440
And this basically the size, so not size.

109
00:07:15,960 --> 00:07:20,550
So what is the end, so and there's nothing that is just in and minus one.

110
00:07:21,910 --> 00:07:26,980
OK, so now let us write the code, so while it starts listing articles to end.

111
00:07:28,790 --> 00:07:31,080
We will find out and we will find out.

112
00:07:31,460 --> 00:07:36,200
So this is nothing but stark lesson battle and the simple case.

113
00:07:37,070 --> 00:07:40,370
So, OK, so first let us find out next in previous.

114
00:07:40,940 --> 00:07:43,250
OK, let us find out next and previous.

115
00:07:43,280 --> 00:07:45,200
So what is next?

116
00:07:47,120 --> 00:07:50,210
It is nothing it is only one plus one.

117
00:07:52,080 --> 00:07:58,350
OK, so my plus one more than more than is necessary to avoid runtime errors.

118
00:07:58,380 --> 00:08:01,440
OK, so plus one more and.

119
00:08:02,670 --> 00:08:09,870
And similarly, you have to find previous so previous made minus one plus and.

120
00:08:10,990 --> 00:08:12,190
And obviously more than.

121
00:08:14,140 --> 00:08:17,850
So after finding the next the previous, we only have to compare.

122
00:08:17,920 --> 00:08:20,020
OK, so let's compare.

123
00:08:21,670 --> 00:08:22,540
So if.

124
00:08:24,170 --> 00:08:27,080
They made this list in the previous.

125
00:08:29,730 --> 00:08:30,290
And.

126
00:08:33,700 --> 00:08:34,539
It's basically.

127
00:08:36,700 --> 00:08:37,750
Less the next.

128
00:08:40,900 --> 00:08:46,620
So what we have to do, we got our answer, OK, so we will simply return our answer.

129
00:08:46,630 --> 00:08:48,010
And what is our answer?

130
00:08:48,010 --> 00:08:49,420
Our answer is AIFMD.

131
00:08:50,670 --> 00:08:51,240
Simple.

132
00:08:52,910 --> 00:08:56,480
OK, so after this, in the elusive condition.

133
00:08:59,160 --> 00:09:04,950
We have to decide whether we have to move left or right and that we can decide with the help of these

134
00:09:04,950 --> 00:09:05,610
conditions.

135
00:09:06,630 --> 00:09:12,870
OK, so if it is less than articles to end after to and equals minus and so.

136
00:09:13,870 --> 00:09:18,130
If murder is less than end, what I have to do.

137
00:09:19,030 --> 00:09:23,050
I have to move in the left hand side, so Andy calls me to my next one.

138
00:09:25,640 --> 00:09:34,400
In the last part, you can write equals one plus one, OK, or if you want to write the complete condition,

139
00:09:34,400 --> 00:09:35,280
you can also write.

140
00:09:35,630 --> 00:09:36,770
So Elif.

141
00:09:38,560 --> 00:09:41,890
Mud is basically going to then start.

142
00:09:44,250 --> 00:09:47,580
OK, simple enough and finally.

143
00:09:49,300 --> 00:09:53,420
OK, so, yeah, so finally, we will get our answer.

144
00:09:53,440 --> 00:09:56,980
OK, so let's turn our court and then we will try to sum it.

145
00:10:01,830 --> 00:10:03,720
OK, so OK, so.

146
00:10:06,400 --> 00:10:07,840
Let's make it capitally.

147
00:10:19,390 --> 00:10:20,980
OK, so what we have to wait.

148
00:10:22,160 --> 00:10:23,990
We have the right return minus one.

149
00:10:24,210 --> 00:10:29,750
OK, this is why we have to write it down minus one, because the convalescing.

150
00:10:31,060 --> 00:10:36,190
They're babies are in danger, so you have to return something, although this line will never be executed.

151
00:10:36,220 --> 00:10:42,260
OK, so line number 21 will never get executed because we will always have a small element.

152
00:10:42,280 --> 00:10:44,310
We will always have a minimum element.

153
00:10:44,380 --> 00:10:47,860
OK, so but it is necessary for the compilation purpose.

154
00:10:48,250 --> 00:10:48,640
OK.

155
00:10:54,620 --> 00:10:55,280
Now, read some.

156
00:11:00,240 --> 00:11:08,700
OK, so our goal is working fine, so this line is only for completion purposes and this line will never

157
00:11:08,700 --> 00:11:09,540
get executed.

158
00:11:09,810 --> 00:11:16,200
OK, so because we will always have the minimum element, we will always have the smallest element.

159
00:11:17,530 --> 00:11:19,460
OK, so this was a very simple code.

160
00:11:19,740 --> 00:11:23,770
Now let's see one more problem where we can use the similar code.

161
00:11:23,920 --> 00:11:26,830
OK, so the problem is basically.

162
00:11:28,340 --> 00:11:31,550
So you have to find how many times a starter that is rotated.

163
00:11:31,880 --> 00:11:36,130
OK, so basically let's discuss one more problem.

164
00:11:36,350 --> 00:11:39,380
So find out how many times.

165
00:11:40,870 --> 00:11:46,010
Assorted arrays rotated, assorted array is rotated.

166
00:11:46,480 --> 00:11:49,510
OK, so let us solve this problem.

167
00:11:49,990 --> 00:11:51,550
So if you can see here.

168
00:11:53,370 --> 00:11:55,810
Let us consider this example, three, four, five, one, two.

169
00:11:56,560 --> 00:12:02,090
OK, so I have this example, three, four, five, one and two.

170
00:12:02,370 --> 00:12:03,810
So how many times?

171
00:12:03,840 --> 00:12:06,270
Basically this area has been rotated.

172
00:12:06,540 --> 00:12:08,610
So let us consider first a small example.

173
00:12:08,640 --> 00:12:10,850
So let us consider this.

174
00:12:10,860 --> 00:12:15,730
So two, three, five, eight, 11 and 12.

175
00:12:15,850 --> 00:12:19,920
OK, so after one rotation, after one rotation, what will happen?

176
00:12:19,930 --> 00:12:20,710
This will come here.

177
00:12:20,730 --> 00:12:21,460
This will come here.

178
00:12:21,480 --> 00:12:22,230
This will come here.

179
00:12:22,260 --> 00:12:22,950
This will come here.

180
00:12:22,980 --> 00:12:23,730
This will come here.

181
00:12:24,150 --> 00:12:25,500
And this will come here.

182
00:12:25,780 --> 00:12:27,540
OK, so this will be the situation.

183
00:12:28,200 --> 00:12:31,670
Well, two, three, five, eight and 11.

184
00:12:31,890 --> 00:12:33,180
So this is one rotation.

185
00:12:34,980 --> 00:12:37,410
OK, now let's do one more rotation.

186
00:12:37,700 --> 00:12:39,960
OK, so this will come here.

187
00:12:39,990 --> 00:12:40,780
This will come here.

188
00:12:40,800 --> 00:12:41,550
This will come here.

189
00:12:41,580 --> 00:12:42,330
This will come here.

190
00:12:42,360 --> 00:12:43,200
This will come here.

191
00:12:43,590 --> 00:12:44,890
And this will come here.

192
00:12:45,180 --> 00:12:46,780
So it will look something like this.

193
00:12:47,310 --> 00:12:49,890
Then we have two, three, five and eight.

194
00:12:50,010 --> 00:12:55,770
OK, now the question is, so basically this question is question is, you are given this, Eddie.

195
00:12:57,560 --> 00:13:05,540
You are given basically assorted rotated, Eddie, and you have to find how many times this area has

196
00:13:05,540 --> 00:13:09,070
been rotated, so the answer in this case will be to.

197
00:13:09,260 --> 00:13:12,830
OK, this is first rotation and the second rotation.

198
00:13:14,450 --> 00:13:19,590
OK, so this is basically our input and this is basically our output.

199
00:13:19,610 --> 00:13:23,840
OK, so we are doing we have done two rotations to obtain this, Eddie.

200
00:13:24,140 --> 00:13:27,530
OK, so how many rotations have been done to obtain this, Eddie?

201
00:13:28,630 --> 00:13:29,860
So this is very simple.

202
00:13:30,160 --> 00:13:35,760
OK, so the rotation is basically the number of rotation is basically nothing.

203
00:13:36,040 --> 00:13:43,120
It is just number of elements before the minimum element.

204
00:13:43,960 --> 00:13:46,470
OK, so these are the number of rotations.

205
00:13:47,170 --> 00:13:49,200
So a number of rotations are nothing.

206
00:13:49,600 --> 00:13:52,730
It is just a number of elements before the minimum element.

207
00:13:53,290 --> 00:13:58,140
OK, so this is the minor element and how many elements are before the element?

208
00:13:58,240 --> 00:13:58,510
Three.

209
00:13:58,870 --> 00:14:01,060
So in this case, our output will be three.

210
00:14:02,050 --> 00:14:08,530
OK, let's set this example only, so this is the smallest element, so how many elements are before

211
00:14:08,530 --> 00:14:09,520
the smallest element?

212
00:14:09,850 --> 00:14:10,170
Two.

213
00:14:10,450 --> 00:14:14,800
So that's why our answer is to OK, so very simple logic.

214
00:14:16,100 --> 00:14:19,820
OK, so if the question is how many times assorted arrays or.

215
00:14:20,930 --> 00:14:21,830
So what do you have to do?

216
00:14:21,860 --> 00:14:28,130
You have to find how many elements are present before the minimum element, OK?

217
00:14:28,370 --> 00:14:30,290
Or in the other way, what can I do?

218
00:14:30,320 --> 00:14:31,090
What can I say?

219
00:14:31,850 --> 00:14:34,120
The number of rotations is basically nothing.

220
00:14:34,130 --> 00:14:42,420
It is the index of the minimum element index of the minor element because the indexing starts from zero.

221
00:14:42,950 --> 00:14:44,140
OK, you can see.

222
00:14:44,360 --> 00:14:48,500
So this is the minimum element and its index is basically three.

223
00:14:48,740 --> 00:14:50,390
So its index is basically two.

224
00:14:50,660 --> 00:14:52,040
This is zero index.

225
00:14:52,340 --> 00:14:54,650
This is one index and this is two index.

226
00:14:54,920 --> 00:14:57,170
And our answer is basically two.

227
00:14:57,800 --> 00:15:02,090
OK, so since the indexing starts from zero, so what can I do?

228
00:15:02,300 --> 00:15:05,270
So number of rotations are basically nothing.

229
00:15:05,660 --> 00:15:09,560
They are just the index of the minimum element.

230
00:15:10,010 --> 00:15:11,400
So here one.

231
00:15:11,870 --> 00:15:13,370
So what is the index of one.

232
00:15:13,370 --> 00:15:14,240
So zero.

233
00:15:14,240 --> 00:15:18,580
One, two, three, two, three is the index of the minimum element.

234
00:15:18,740 --> 00:15:22,380
So that's why our answer for this input will be three.

235
00:15:22,430 --> 00:15:23,710
As you can see here, three.

236
00:15:24,550 --> 00:15:30,590
OK, so if the question is how many times assorted error is audited, what do you have to do?

237
00:15:30,770 --> 00:15:36,400
You have to just find out the index of the minimum element and how to find out the index of the minimum

238
00:15:36,410 --> 00:15:36,830
element.

239
00:15:37,160 --> 00:15:39,950
So we have already solved this question if we see above.

240
00:15:41,080 --> 00:15:47,620
OK, so if you see about what we are doing here, so what we are doing here, we are finding out the

241
00:15:47,620 --> 00:15:48,360
minimum element.

242
00:15:48,940 --> 00:15:53,620
So instead of finding out the minimum element, I will find out the index of the minimum element.

243
00:15:53,890 --> 00:15:55,170
Basically what we have to do.

244
00:15:55,540 --> 00:15:57,220
So instead of returning.

245
00:15:57,220 --> 00:16:04,470
So if we can see here, if the question is if the question is find out the index.

246
00:16:04,480 --> 00:16:07,450
So instead of returning the minimum element, what I will do.

247
00:16:09,650 --> 00:16:11,060
So what I will do, I will return.

248
00:16:11,900 --> 00:16:14,180
OK, so this is our second question.

249
00:16:15,160 --> 00:16:18,980
Question is how many times a soldier that is rotated?

250
00:16:19,040 --> 00:16:28,400
OK, so if the question is how many times assorted error is rotated, then what do you have to do?

251
00:16:29,730 --> 00:16:36,750
Basically, you have to return mid, you will return them with you will return the index.

252
00:16:37,050 --> 00:16:37,470
OK.

253
00:16:39,940 --> 00:16:42,680
So that's all OK, I'm repeating myself.

254
00:16:44,650 --> 00:16:50,600
So basically this whole code is for solving it, for finding out the minimum element.

255
00:16:50,800 --> 00:16:53,900
OK, so we are finding out the minimum element.

256
00:16:53,920 --> 00:16:56,440
So this is our minimum element.

257
00:16:57,070 --> 00:17:01,990
Now, if the question is how many times assorted errors are treated, then what do you have to do?

258
00:17:02,350 --> 00:17:04,930
You can see here what we are doing.

259
00:17:06,119 --> 00:17:12,030
So what we are doing, our logic is basically saying you just find out the index of the minimum element

260
00:17:12,240 --> 00:17:13,619
and what is the index?

261
00:17:13,630 --> 00:17:15,109
So index is basically nothing.

262
00:17:15,119 --> 00:17:16,020
It is just it.

263
00:17:16,560 --> 00:17:19,560
OK, so this can be the variation of this problem.

264
00:17:19,589 --> 00:17:22,890
OK, so the variation of this problem can be this one.

265
00:17:24,270 --> 00:17:28,440
So the court will be saying everything, the logic and the court, everything will be the same.

266
00:17:28,620 --> 00:17:35,490
So instead of returning, array of you will return unlabelled minus the index of military value.

267
00:17:36,770 --> 00:17:45,260
OK, so I hope you understood this cold, OK, so if you have any doubt in this question, you can ask

268
00:17:45,260 --> 00:17:45,990
me, OK?

269
00:17:46,030 --> 00:17:47,450
So I think we discussed.

270
00:17:48,920 --> 00:17:55,940
OK, so, yes, since we used to buy any such approach in discussion, so the time complexities basically

271
00:17:55,940 --> 00:18:03,020
login, so the time complexities basically go off log in where and is the size of the area and the space

272
00:18:03,020 --> 00:18:04,280
complexities or DRAFFIN.

273
00:18:04,550 --> 00:18:06,440
We are not using any extra space.

274
00:18:07,110 --> 00:18:10,880
OK, so we have discussed the time of the space complexity.

275
00:18:11,240 --> 00:18:13,820
We have discussed one more variation of this problem.

276
00:18:14,750 --> 00:18:15,650
OK, thank you.

