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.