1 00:00:00,090 --> 00:00:00,720 What's up, guys? 2 00:00:00,810 --> 00:00:04,740 Andy, here we are living together into day, free of the from zero to hero challenge. 3 00:00:05,040 --> 00:00:06,090 And I've prepared for you. 4 00:00:06,120 --> 00:00:12,660 An awesome problem which actually has a smart solution, which uses my favorite ever data structures. 5 00:00:12,960 --> 00:00:15,770 A very simple one, but super powerful. 6 00:00:15,840 --> 00:00:20,040 First of all, if you really like this Vidor's and want more, make sure to stay in tune by clicking 7 00:00:20,040 --> 00:00:20,910 the subscribe button. 8 00:00:21,150 --> 00:00:23,820 Make sure your like the videos and support this, Jenna. 9 00:00:24,300 --> 00:00:25,560 Your job is to make it happen. 10 00:00:25,740 --> 00:00:27,270 As always, my job is to make it awesome. 11 00:00:27,450 --> 00:00:29,310 So let us read the statement together. 12 00:00:29,850 --> 00:00:32,130 The problem is called one free two pattern. 13 00:00:32,280 --> 00:00:34,590 And given a sequence of N integers. 14 00:00:34,710 --> 00:00:35,450 A1, a2. 15 00:00:35,580 --> 00:00:36,000 Dot, dot. 16 00:00:36,000 --> 00:00:36,210 Dot. 17 00:00:36,450 --> 00:00:38,760 And what is the one free to better? 18 00:00:38,870 --> 00:00:43,370 A one free two pattern is a subsequence A.I., A.J. and AK. 19 00:00:43,540 --> 00:00:43,760 Right. 20 00:00:43,820 --> 00:00:47,680 So free numbers from the array where I is less than G. 21 00:00:48,030 --> 00:00:48,300 J. 22 00:00:48,360 --> 00:00:52,710 There's a K and a of AI is less than A of K which is less than a of J. 23 00:00:53,010 --> 00:00:53,280 Right. 24 00:00:53,550 --> 00:00:56,160 So the first number eight is the smallest one. 25 00:00:56,250 --> 00:00:59,340 Then the second smallest number is a K. 26 00:00:59,640 --> 00:00:59,910 Right. 27 00:00:59,970 --> 00:01:03,240 And that the biggest number from this free is the second one. 28 00:01:03,510 --> 00:01:05,060 That's why one free to factor. 29 00:01:05,190 --> 00:01:05,430 Right. 30 00:01:05,910 --> 00:01:10,530 So design an algorithm that takes the list of our numbers as input and checks, whether there is a one 31 00:01:10,530 --> 00:01:11,610 free two pattern in the list. 32 00:01:12,240 --> 00:01:15,480 Also, let's just open our notepad, as always. 33 00:01:16,020 --> 00:01:17,730 And take the first example. 34 00:01:17,790 --> 00:01:20,430 So example number one is one, two, three, four. 35 00:01:20,610 --> 00:01:20,910 Right. 36 00:01:21,270 --> 00:01:27,690 So obvious we don't have free numbers to satisfy that because the array is increasing disorder, but 37 00:01:27,690 --> 00:01:29,250 not for free. 38 00:01:29,310 --> 00:01:31,290 One for two, we should return. 39 00:01:31,290 --> 00:01:31,650 True. 40 00:01:32,100 --> 00:01:34,260 Because the one free true pattern. 41 00:01:34,740 --> 00:01:35,370 What is it. 42 00:01:35,610 --> 00:01:37,890 Is free for two or one. 43 00:01:37,890 --> 00:01:38,430 Four two. 44 00:01:38,940 --> 00:01:39,170 Right. 45 00:01:39,630 --> 00:01:40,140 This is good. 46 00:01:40,380 --> 00:01:45,360 So free for two or maybe one for two. 47 00:01:45,360 --> 00:01:45,690 Right. 48 00:01:46,200 --> 00:01:49,800 The first element is the smallest one then is the third one. 49 00:01:49,830 --> 00:01:50,190 Right. 50 00:01:50,340 --> 00:01:51,770 Is the second smallest one. 51 00:01:51,780 --> 00:01:54,570 And then the second one from this is the biggest one. 52 00:01:55,170 --> 00:01:55,590 So. 53 00:01:57,230 --> 00:01:59,410 Let's start thinking about this problem. 54 00:02:00,200 --> 00:02:01,280 And as always, guys. 55 00:02:02,310 --> 00:02:05,880 You probably if you watched my last videos, you probably got used to it. 56 00:02:06,180 --> 00:02:08,920 We always start by brute force approaches. 57 00:02:08,970 --> 00:02:09,270 Right. 58 00:02:09,570 --> 00:02:12,570 So I want the worst brute force approach ever. 59 00:02:12,720 --> 00:02:17,430 And that is Biegel of MQ Starbase brute force number one. 60 00:02:17,490 --> 00:02:17,810 Right. 61 00:02:17,910 --> 00:02:20,510 Brute force number one, which is Bigo of and cute. 62 00:02:21,000 --> 00:02:21,630 What shall I do? 63 00:02:22,080 --> 00:02:23,510 I should fix each number. 64 00:02:23,760 --> 00:02:24,030 Right. 65 00:02:24,270 --> 00:02:25,790 So make a for loop four. 66 00:02:25,870 --> 00:02:27,560 I make another for loop for J. 67 00:02:27,600 --> 00:02:28,260 Make another four. 68 00:02:28,260 --> 00:02:28,820 Loop for K. 69 00:02:28,830 --> 00:02:29,090 Right. 70 00:02:29,400 --> 00:02:31,620 So fix each of those. 71 00:02:31,830 --> 00:02:34,120 Fix I fix. 72 00:02:34,390 --> 00:02:35,490 Jake fix king. 73 00:02:36,180 --> 00:02:38,050 Check if they are valid. 74 00:02:38,110 --> 00:02:40,920 So I use less than a half ks less than a day. 75 00:02:41,220 --> 00:02:42,150 If it is return. 76 00:02:42,150 --> 00:02:42,430 True. 77 00:02:42,720 --> 00:02:44,220 If not, continue checking. 78 00:02:44,430 --> 00:02:47,700 In the end, if you haven't find a solution, you are a mystery to enforce. 79 00:02:48,130 --> 00:02:48,450 So. 80 00:02:49,510 --> 00:02:49,870 All right. 81 00:02:50,330 --> 00:02:51,230 This is super simple. 82 00:02:51,890 --> 00:02:56,980 Let's try to find another brute force, which now to be M squared. 83 00:02:57,620 --> 00:02:59,210 So brute force. 84 00:03:01,280 --> 00:03:05,020 Number two, I want something in Bigo of Arms Sweat. 85 00:03:06,260 --> 00:03:08,600 And let's be smart about that, right? 86 00:03:09,000 --> 00:03:10,450 For Biegel of any cube. 87 00:03:11,240 --> 00:03:13,370 We could fix all those free positions. 88 00:03:13,460 --> 00:03:17,120 I J and K now for Begal of M squared. 89 00:03:17,780 --> 00:03:19,810 We won't fix all the free of them. 90 00:03:20,330 --> 00:03:21,770 We are going to fix only two of them. 91 00:03:22,400 --> 00:03:24,860 And which ones should we fix. 92 00:03:25,620 --> 00:03:25,880 Well. 93 00:03:27,240 --> 00:03:28,320 I don't think it matters at all. 94 00:03:28,830 --> 00:03:34,410 So I am going to fix, let's say, fix or changing. 95 00:03:34,890 --> 00:03:35,160 Right. 96 00:03:35,490 --> 00:03:36,270 So the last two of them. 97 00:03:36,270 --> 00:03:37,970 Right when I fixed K. 98 00:03:39,160 --> 00:03:39,430 Right. 99 00:03:39,570 --> 00:03:41,060 So it's actually gently. 100 00:03:41,190 --> 00:03:42,050 This is your right. 101 00:03:42,330 --> 00:03:44,490 So fixing janky and I should check. 102 00:03:45,000 --> 00:03:50,030 If so, check if ACA is less than aging. 103 00:03:50,070 --> 00:03:50,550 First of all. 104 00:03:50,550 --> 00:03:50,820 Right. 105 00:03:51,300 --> 00:03:54,550 And if it is, I should find the missing eye. 106 00:03:55,160 --> 00:03:55,860 And what should I do? 107 00:03:56,310 --> 00:04:00,080 I should see if there is an eye which is less than G. 108 00:04:00,720 --> 00:04:01,430 Such as. 109 00:04:01,680 --> 00:04:06,660 So check if there is some eye. 110 00:04:07,220 --> 00:04:07,510 Right. 111 00:04:08,010 --> 00:04:08,830 Which is less than G. 112 00:04:09,240 --> 00:04:09,540 Right. 113 00:04:09,840 --> 00:04:12,160 And what should be the property of a right. 114 00:04:12,670 --> 00:04:14,220 Obviously it's less than achy. 115 00:04:14,820 --> 00:04:18,560 So and a I it's less than 80. 116 00:04:18,960 --> 00:04:20,190 But how should I check this. 117 00:04:20,490 --> 00:04:21,300 I should take this in. 118 00:04:21,300 --> 00:04:23,130 Konstantine writes on Bigo of one. 119 00:04:23,640 --> 00:04:26,970 So I want you to imagine right now we have fixed J and K. 120 00:04:27,600 --> 00:04:27,870 Right. 121 00:04:28,320 --> 00:04:31,680 And we have seen that A of J. 122 00:04:31,950 --> 00:04:33,290 Is bigger than JFK. 123 00:04:33,870 --> 00:04:39,030 And now what we want here is to find some eye less than G. 124 00:04:39,480 --> 00:04:42,510 Such as a Y is less than a of key. 125 00:04:43,660 --> 00:04:44,110 So. 126 00:04:45,100 --> 00:04:51,980 The question is, do I have an element from position one to position Jay minus one? 127 00:04:53,180 --> 00:04:58,010 Which has a value less than some given value, which is obviously AK. 128 00:04:59,030 --> 00:05:05,570 So if I have to try to find an element from some range less than other value. 129 00:05:07,230 --> 00:05:11,240 The perfect candidate for that is going to be the minimum element from that range. 130 00:05:11,670 --> 00:05:11,940 Right. 131 00:05:12,210 --> 00:05:17,340 So doesn't make any sense to take the greatest element from position one to position Jay minus one. 132 00:05:18,910 --> 00:05:24,490 When I can check the smallest one, because the smallest one has the higher odds to be less than AFIK. 133 00:05:25,270 --> 00:05:26,280 So this is Mark, right? 134 00:05:26,680 --> 00:05:32,590 So what I should basically do in order to check this in Konstantine is that I should know the minimum 135 00:05:32,710 --> 00:05:34,770 value from some prefix. 136 00:05:35,110 --> 00:05:35,740 Very quick. 137 00:05:36,690 --> 00:05:41,010 And how do we know some value very quick in Bigo of one? 138 00:05:41,490 --> 00:05:42,030 Exactly. 139 00:05:42,210 --> 00:05:43,140 Pre computing it. 140 00:05:43,360 --> 00:05:45,320 So we shall have another. 141 00:05:45,630 --> 00:05:47,370 We shall have, let's say, mean value. 142 00:05:47,580 --> 00:05:47,850 Right. 143 00:05:48,480 --> 00:05:51,680 We should have an auxiliary array, which is mean value. 144 00:05:52,470 --> 00:05:54,510 Which is going to have the minimum. 145 00:05:55,280 --> 00:05:56,700 The minimum value. 146 00:05:56,970 --> 00:05:57,270 Right. 147 00:05:58,140 --> 00:05:59,370 B to in. 148 00:06:00,330 --> 00:06:05,290 The minimal barrier between a one, a two that are that a right? 149 00:06:05,460 --> 00:06:07,380 So the value of this preface. 150 00:06:07,860 --> 00:06:13,690 Now, if I could disagree, which is obviously linear time to pre compute, right? 151 00:06:13,920 --> 00:06:17,220 It's like the partial sums, but it's basic, you know, a partial minimum. 152 00:06:18,390 --> 00:06:23,690 After I can do this great, I will know my information in constant time, which is awesome, right? 153 00:06:24,120 --> 00:06:24,540 So. 154 00:06:26,260 --> 00:06:31,480 Meanwell of life is basically the minimum between minivan of minus one. 155 00:06:31,680 --> 00:06:36,490 So the minimum between the first minus one element and now my current element, which is eight. 156 00:06:37,270 --> 00:06:37,480 Right. 157 00:06:38,070 --> 00:06:39,540 All of this in a Ford Loop. 158 00:06:40,540 --> 00:06:46,290 So Ford is going to be from position one, let's say, all the way to position. 159 00:06:46,310 --> 00:06:52,980 And plus plus I would have the minivan after computing its other three, computing the minivan I should 160 00:06:52,980 --> 00:06:53,320 fix. 161 00:06:53,340 --> 00:07:03,480 Jay and Kate, we've tested for loops and I should check if A of Kate is less than A.J. and most important, 162 00:07:03,840 --> 00:07:06,510 the minivan of J minus one. 163 00:07:07,490 --> 00:07:09,610 His heart is less than a game. 164 00:07:10,100 --> 00:07:17,660 And if it is, we should return to right away, if not after executing these two nested for loops. 165 00:07:18,080 --> 00:07:19,670 We know that we won't have a solution. 166 00:07:19,770 --> 00:07:20,610 So return false. 167 00:07:21,080 --> 00:07:21,500 Perfect. 168 00:07:22,070 --> 00:07:23,600 So this is the second brute force approach. 169 00:07:23,630 --> 00:07:24,680 B, go off and square. 170 00:07:25,170 --> 00:07:28,910 Now let's dive into the optimal solution, which is linear time. 171 00:07:29,060 --> 00:07:29,330 Right. 172 00:07:29,720 --> 00:07:34,100 So optimal solution is going to be pretty amazing, actually. 173 00:07:34,430 --> 00:07:35,000 Is of. 174 00:07:35,190 --> 00:07:40,340 And so I want you to post this video right now and think about the optimal solution, because obviously 175 00:07:40,400 --> 00:07:44,960 we didn't we haven't gone through this brute force approaches because they are useless. 176 00:07:44,960 --> 00:07:45,230 Right. 177 00:07:45,500 --> 00:07:48,680 So the brute force approach number two will help. 178 00:07:48,680 --> 00:07:51,260 You will be the foundation to find your optimal solution. 179 00:07:51,470 --> 00:07:52,850 Post the video and think about it. 180 00:07:54,020 --> 00:07:54,620 Perfect eyes. 181 00:07:55,100 --> 00:07:56,270 I hope as many as you can. 182 00:07:56,270 --> 00:07:57,290 The optimal solution, right? 183 00:07:57,650 --> 00:07:58,550 It's not an easy one. 184 00:07:58,820 --> 00:08:01,340 It's quite tricky, but it's super awesome. 185 00:08:01,580 --> 00:08:07,670 And we are going to dive into my favorite data structure, which is the most basic one. 186 00:08:08,170 --> 00:08:08,720 The stack. 187 00:08:09,170 --> 00:08:11,590 This problem is going to use the stack to be solved. 188 00:08:11,900 --> 00:08:13,380 But now this is my end. 189 00:08:13,790 --> 00:08:17,560 If you want to think again of the problem, knowing that it's solved this stack, Bill, I guess. 190 00:08:17,990 --> 00:08:20,240 And we are going to take this step by step. 191 00:08:20,310 --> 00:08:29,870 So individual support number two, we have fixed J and K and found that our favorite, a the most favorable 192 00:08:29,870 --> 00:08:35,370 candidate is the minimum value from the prefix from position one to do minus one. 193 00:08:35,390 --> 00:08:35,630 Right. 194 00:08:36,150 --> 00:08:41,020 Right now for Biegel of am I not able anymore to fix J. 195 00:08:41,150 --> 00:08:41,420 K. 196 00:08:41,900 --> 00:08:43,730 So I should fix only one of those. 197 00:08:43,790 --> 00:08:50,960 And I am going to share with you a super powerful trick which is used in 99 percent of these kinds of 198 00:08:50,960 --> 00:08:51,260 problem. 199 00:08:51,860 --> 00:08:55,920 When you have to find or fix free pointers, I, j and K, right. 200 00:08:56,240 --> 00:08:59,630 But because of the time complexity, you could only fix one of those. 201 00:08:59,960 --> 00:09:00,810 You always fix them. 202 00:09:00,810 --> 00:09:01,310 Middle one. 203 00:09:01,700 --> 00:09:01,970 Right. 204 00:09:02,480 --> 00:09:06,830 So it is the most useful to fix G. 205 00:09:07,460 --> 00:09:09,800 So I am making a for loop for only fixing G. 206 00:09:10,530 --> 00:09:14,060 Now let's take a look again at the brute force approach number two. 207 00:09:14,090 --> 00:09:18,620 And remember that when we fixed J and K, we know that I write that minimum value. 208 00:09:19,040 --> 00:09:19,880 That's our I. 209 00:09:20,180 --> 00:09:21,200 D still false. 210 00:09:21,890 --> 00:09:28,490 Now I don't know the k k could be everything between J plus one an N, but I still the most favorable 211 00:09:28,500 --> 00:09:31,370 I is going to be the minimum element from the prefix. 212 00:09:31,550 --> 00:09:32,540 So I fix the J. 213 00:09:33,020 --> 00:09:33,350 I know. 214 00:09:33,350 --> 00:09:34,720 What is the I write. 215 00:09:35,060 --> 00:09:40,310 So I is the position of a minivan basically of J minus one. 216 00:09:40,730 --> 00:09:40,970 Right. 217 00:09:41,570 --> 00:09:44,270 And now I should find if there is a K. 218 00:09:44,660 --> 00:09:48,740 So we should check in Konstantine if. 219 00:09:49,720 --> 00:09:52,810 There is some key such buzz. 220 00:09:53,200 --> 00:09:54,100 Well, first of all. 221 00:09:55,710 --> 00:09:57,020 Often we find Mike. 222 00:09:58,210 --> 00:10:00,090 I should check if I mgd our venue. 223 00:10:00,250 --> 00:10:00,520 Right. 224 00:10:00,850 --> 00:10:07,000 So obviously what we know here is that AIG should be less than AIG. 225 00:10:07,170 --> 00:10:07,420 Right. 226 00:10:07,810 --> 00:10:09,860 So first of all, reject this check. 227 00:10:09,870 --> 00:10:10,090 Give. 228 00:10:10,780 --> 00:10:11,050 Right. 229 00:10:11,290 --> 00:10:15,920 And if this holds perfect, we should go on and find the key. 230 00:10:15,970 --> 00:10:16,690 If there is one. 231 00:10:16,960 --> 00:10:18,790 So check if there is some key. 232 00:10:18,850 --> 00:10:19,720 Such as. 233 00:10:20,850 --> 00:10:24,800 This case should be between these venues, right? 234 00:10:25,230 --> 00:10:28,380 So this case should be less than A.J.. 235 00:10:29,960 --> 00:10:33,050 But should be greater than a. 236 00:10:36,340 --> 00:10:43,150 Well, remember that I have fixed my jeep and they know my AOF, right? 237 00:10:43,540 --> 00:10:43,800 Right. 238 00:10:44,410 --> 00:10:46,150 So when I fix my jeep. 239 00:10:46,330 --> 00:10:49,360 That is the maximum value between this free and. 240 00:10:50,400 --> 00:10:54,770 He of K should be less than this and greater than a of all. 241 00:10:55,520 --> 00:10:56,750 So eight of K. 242 00:10:58,270 --> 00:11:03,850 Should be what is the, let's say, most favorable element? 243 00:11:04,770 --> 00:11:09,170 Right from the position J plus one to the position M. 244 00:11:10,340 --> 00:11:11,630 Which could hold this. 245 00:11:12,580 --> 00:11:14,970 What is the maximum value? 246 00:11:15,490 --> 00:11:17,910 Which is less than a of J. 247 00:11:18,520 --> 00:11:18,820 Right. 248 00:11:19,180 --> 00:11:21,020 So it should be less than a J. 249 00:11:21,610 --> 00:11:24,010 But in order to be greater than a of I. 250 00:11:25,190 --> 00:11:27,410 The best candidate is the maximum vote. 251 00:11:27,860 --> 00:11:37,460 So EFCA should be the maximum value from this range or from the range from J plus one all the way to 252 00:11:37,460 --> 00:11:39,090 position N, right. 253 00:11:39,620 --> 00:11:43,550 Which is less than a J. 254 00:11:44,970 --> 00:11:45,600 And that's perfect. 255 00:11:45,660 --> 00:11:46,860 Is that what we want? 256 00:11:47,190 --> 00:11:49,540 We want to find out if there is some key. 257 00:11:49,650 --> 00:11:49,980 Right. 258 00:11:50,070 --> 00:11:54,080 Again, the maximum value from Geep US one, an end, which is less than a of G. 259 00:11:54,360 --> 00:11:57,270 So we need to find this value really quick. 260 00:11:57,390 --> 00:11:58,250 In Bigo of one. 261 00:11:58,870 --> 00:12:03,370 Now what is the difference between this and what we had to find a brute force approach. 262 00:12:03,390 --> 00:12:04,830 Number two in the brute force approach. 263 00:12:04,830 --> 00:12:08,310 Number two, we had to find the minimum value from some prefix. 264 00:12:08,670 --> 00:12:12,990 Right now we have to find the maximum value from some suffix. 265 00:12:13,020 --> 00:12:13,260 Right. 266 00:12:13,290 --> 00:12:16,560 Because it's from some position all the way to end to the end of the array. 267 00:12:17,070 --> 00:12:20,760 But the maximum value, which is less than some given value. 268 00:12:21,420 --> 00:12:27,090 So it's not enough just to compute a personal maximum or suffixes or something like that. 269 00:12:27,450 --> 00:12:32,400 We need something stronger and that something stronger is the step. 270 00:12:32,750 --> 00:12:33,010 Right. 271 00:12:33,240 --> 00:12:34,650 And how will we use the stack? 272 00:12:35,330 --> 00:12:38,700 Well, we will go with our G. 273 00:12:39,780 --> 00:12:43,800 We are going to iterate from the end of the array all the way to the beginning. 274 00:12:44,250 --> 00:12:45,210 And why is that? 275 00:12:45,420 --> 00:12:52,890 Because when we are at some G, we will have already iterate through the elements on his right, which 276 00:12:52,890 --> 00:12:56,340 are our possible maximum value, our possible case. 277 00:12:56,550 --> 00:12:56,820 Right. 278 00:12:57,240 --> 00:12:59,290 So I am going to go if this G. 279 00:12:59,370 --> 00:13:03,360 Starting from position and all the way to position one in G minus minus. 280 00:13:03,480 --> 00:13:07,410 And here we have actually two possibilities because we could ever use a set. 281 00:13:07,710 --> 00:13:07,950 Right. 282 00:13:08,040 --> 00:13:13,890 Remember what is a set I said is a collection which stores our elements increasingly or decreasing the 283 00:13:13,890 --> 00:13:14,430 sorting. 284 00:13:14,820 --> 00:13:17,000 So if we store a set here. 285 00:13:18,130 --> 00:13:25,330 We basically have iterated for all the elements between J plus one position, give us one and M we basically 286 00:13:25,330 --> 00:13:27,230 added each element in our set, right? 287 00:13:27,280 --> 00:13:31,590 So when iterating for an element, inserting it into our set, the city's increasingly sorted. 288 00:13:31,630 --> 00:13:35,050 And we can perform lower and upper bound on this set. 289 00:13:35,590 --> 00:13:37,220 So we have the lower and upper bound. 290 00:13:37,240 --> 00:13:42,760 We can binary search basically the first greater element or the last less or equal element from that 291 00:13:42,760 --> 00:13:43,120 set. 292 00:13:43,690 --> 00:13:45,490 Which is perfect because solves our problem. 293 00:13:45,490 --> 00:13:45,760 Right. 294 00:13:46,030 --> 00:13:48,200 The maximum value, which is less than a. 295 00:13:48,670 --> 00:13:50,070 Which is less than a G. 296 00:13:50,740 --> 00:13:57,420 So if our set is increasingly sorted and we perform the lower bound on eight of G. 297 00:13:57,940 --> 00:14:04,420 And then we decrement one time that iterator, we are going to have the maximum value, which is strictly 298 00:14:04,420 --> 00:14:05,330 less than a G. 299 00:14:05,860 --> 00:14:07,330 So a possible solution. 300 00:14:07,600 --> 00:14:12,040 Basically I can write here O brute force approach. 301 00:14:13,030 --> 00:14:13,330 Right. 302 00:14:13,690 --> 00:14:17,890 So this is it's not actually brute force approach because it's super good in time. 303 00:14:18,220 --> 00:14:22,720 But just for the fun of it, let's say it's a brute force approach between because we are better than 304 00:14:22,720 --> 00:14:22,960 that. 305 00:14:23,140 --> 00:14:23,400 Right. 306 00:14:23,650 --> 00:14:24,890 So in Biegel of Ms. 307 00:14:25,200 --> 00:14:25,700 Logan. 308 00:14:26,040 --> 00:14:26,300 Right. 309 00:14:26,950 --> 00:14:27,730 Using a set. 310 00:14:28,000 --> 00:14:30,040 We have this for brute force approach. 311 00:14:30,700 --> 00:14:31,000 Not. 312 00:14:32,420 --> 00:14:41,180 The beauty of this solution of the bigo of an optimal solution is that we can get rid of the set to 313 00:14:41,420 --> 00:14:43,190 using the stick and follow me. 314 00:14:43,850 --> 00:14:49,550 As you might know, if you have some experience with sex when using the stick, we will basically have 315 00:14:49,610 --> 00:14:53,960 some elements into the stack sorted, either increasingly or decreasing. 316 00:14:54,080 --> 00:14:54,410 Right. 317 00:14:54,920 --> 00:14:59,360 So what should be the order of our elements in our stack here? 318 00:14:59,930 --> 00:15:03,710 Well, we need all the elements which are of less than a of G. 319 00:15:04,460 --> 00:15:09,140 So when we are at some element, I need to eat a rate in my stack. 320 00:15:09,230 --> 00:15:11,090 All the elements less than me. 321 00:15:11,480 --> 00:15:16,040 So we are going to have a stacked non increasingly sort of right. 322 00:15:16,140 --> 00:15:18,760 Mawn increasingly or buy new shoes. 323 00:15:18,800 --> 00:15:19,040 Good. 324 00:15:19,670 --> 00:15:20,240 Sorted. 325 00:15:20,720 --> 00:15:21,020 Right. 326 00:15:21,440 --> 00:15:24,620 Because if we have our in on increasingly sorted. 327 00:15:24,660 --> 00:15:24,920 All right. 328 00:15:24,950 --> 00:15:29,780 Let's suppose it's then six, five, two or three free again. 329 00:15:29,780 --> 00:15:35,960 And one when we have some value, let's say when we are at the step, AIG equals seven. 330 00:15:36,800 --> 00:15:39,230 We are iterating from the top of the stack. 331 00:15:39,470 --> 00:15:39,770 Right. 332 00:15:39,830 --> 00:15:42,300 Always we are taking element from the top of the stack. 333 00:15:42,560 --> 00:15:46,290 And those elements are going to be less than my seven. 334 00:15:47,240 --> 00:15:50,680 If it was increasingly sorted, I would have started with the maximum. 335 00:15:51,140 --> 00:15:55,310 So I wouldn't cover my less elements right from the stack. 336 00:15:55,550 --> 00:15:59,940 So we are keeping a stack which is sorted decreasingly or non increasingly. 337 00:16:00,200 --> 00:16:00,520 Right. 338 00:16:00,890 --> 00:16:06,560 And each time we are in some position G and we want to insert that element in our stack. 339 00:16:06,890 --> 00:16:12,410 First of all, in order to maintain this stack in the non increasingly sorted order, we have to get 340 00:16:12,410 --> 00:16:16,640 rid of those elements from the top, which are less than my value. 341 00:16:17,210 --> 00:16:20,040 So we are basically iterating for all the elements. 342 00:16:20,060 --> 00:16:20,750 Less than me. 343 00:16:21,800 --> 00:16:24,290 We are going to try out each of these elements, right? 344 00:16:24,320 --> 00:16:29,300 So we are going to encounter at some point the maximum right from that state, which is awesome. 345 00:16:29,690 --> 00:16:32,690 And we are going to pop those from the state and then add my element. 346 00:16:32,930 --> 00:16:37,190 So here I will have one free, free five and six. 347 00:16:37,500 --> 00:16:39,890 Try each of those to be my possible key. 348 00:16:40,520 --> 00:16:47,360 If one of them is so it's basically I know that it's no less than A.J. I should check if these elements 349 00:16:47,390 --> 00:16:50,870 are greater than eight, if I find one return true. 350 00:16:51,230 --> 00:16:53,550 If not, I would just continue my algorithm. 351 00:16:53,570 --> 00:16:58,500 These elements are now gone from my stack and I add my seven and continue the algorithm right now. 352 00:16:58,940 --> 00:17:01,190 Why is the complexity of this big, all of em? 353 00:17:01,760 --> 00:17:03,640 Because you should know this. 354 00:17:04,690 --> 00:17:05,280 You must think. 355 00:17:06,270 --> 00:17:09,390 Of course, at some point we are going to remove more than one element. 356 00:17:09,420 --> 00:17:09,720 Right. 357 00:17:10,140 --> 00:17:16,680 So you might think that, oh, this thing isn't bigger event squared because we have N elements. 358 00:17:16,740 --> 00:17:21,480 And for each element before inserting it to the stake, we are popping a lot of elements. 359 00:17:21,840 --> 00:17:24,210 And it's not because there's some stake, if you think about it. 360 00:17:24,240 --> 00:17:27,750 Each element is inserted and popped from the stake exactly once. 361 00:17:28,170 --> 00:17:29,970 And we have in our array and elements. 362 00:17:30,000 --> 00:17:30,300 Right. 363 00:17:30,480 --> 00:17:35,140 So an alliance crossed two operations, one insertion and one removal is big off. 364 00:17:35,320 --> 00:17:36,990 That makes us not. 365 00:17:37,170 --> 00:17:38,400 We have the optimal solution. 366 00:17:38,760 --> 00:17:40,730 Let's jump into lead code and write the code for it. 367 00:17:40,770 --> 00:17:46,010 By the way, that code is an amazing platform, the perfect plan for preparing for technical endeavors. 368 00:17:46,020 --> 00:17:46,260 Right. 369 00:17:46,380 --> 00:17:47,220 So make sure you check it out. 370 00:17:47,730 --> 00:17:49,530 Not for implementing this. 371 00:17:49,980 --> 00:17:52,780 We have an argument, which is a vector of integer numbers. 372 00:17:53,190 --> 00:17:54,830 And I am going to use my stack. 373 00:17:54,930 --> 00:17:58,440 So stack of integers as team, let's say in this deck. 374 00:17:58,470 --> 00:18:01,440 I'm not going to hold my elements right there. 375 00:18:01,470 --> 00:18:01,940 Values. 376 00:18:01,980 --> 00:18:03,810 I'm going to fold positions. 377 00:18:04,250 --> 00:18:04,520 Right. 378 00:18:04,860 --> 00:18:15,360 So basically here is the boysie shots of my Norn increasingly sorted elements and elements. 379 00:18:16,170 --> 00:18:16,380 Right. 380 00:18:16,410 --> 00:18:16,860 Perfect. 381 00:18:17,040 --> 00:18:21,210 Not the main for loop, which we said is going to be for the G. 382 00:18:21,450 --> 00:18:23,580 So we've the G starting that position. 383 00:18:23,610 --> 00:18:25,050 So we are here in nums. 384 00:18:25,410 --> 00:18:25,830 All right. 385 00:18:26,220 --> 00:18:27,150 First things first. 386 00:18:27,360 --> 00:18:28,050 First things first. 387 00:18:28,320 --> 00:18:29,840 We should compute that mean event array. 388 00:18:30,000 --> 00:18:30,240 Right. 389 00:18:30,270 --> 00:18:31,200 This is super important. 390 00:18:31,410 --> 00:18:37,410 So for the sake of this example, I am even going to use the vectors because is the way to do it. 391 00:18:37,650 --> 00:18:40,820 So vector of integer max not its meaning then. 392 00:18:41,190 --> 00:18:41,430 Right. 393 00:18:41,940 --> 00:18:44,620 We are computing minimum's so mean Val of. 394 00:18:45,150 --> 00:18:50,490 First of all let's take into one variable the size of the nums vector. 395 00:18:50,730 --> 00:18:52,840 So M equals nums dot sight. 396 00:18:53,880 --> 00:18:57,180 Right now we have the size of the of these vector nums. 397 00:18:57,720 --> 00:19:02,920 And after getting the size we are going to compute the minivan. 398 00:19:03,030 --> 00:19:04,350 So let's just define it. 399 00:19:04,650 --> 00:19:08,550 Meanwhile is going to be an array consisting of M elements. 400 00:19:08,700 --> 00:19:09,030 Right. 401 00:19:09,390 --> 00:19:10,880 And each of those I don't know. 402 00:19:11,010 --> 00:19:12,610 They don't have initially some value. 403 00:19:12,620 --> 00:19:12,870 Right. 404 00:19:13,230 --> 00:19:17,250 So this is basically a constructor right here with this N. 405 00:19:17,580 --> 00:19:22,070 I am constructing a vector of integers, which has initially already N elements. 406 00:19:22,110 --> 00:19:22,410 Right. 407 00:19:23,460 --> 00:19:23,820 Perfect. 408 00:19:24,030 --> 00:19:27,020 Now let's compute the mean event vector. 409 00:19:27,390 --> 00:19:34,500 And first of all, the mean Val one position zero is going to be the element of position zero from us. 410 00:19:34,830 --> 00:19:36,060 So I mean Val of zero Islams. 411 00:19:36,340 --> 00:19:41,510 Then I will make a for loop starting a position one less than N. 412 00:19:41,730 --> 00:19:41,970 Right. 413 00:19:42,000 --> 00:19:49,300 Because vectors are zero indexed superimportant plus plus and mean val of eyes is going to be the minimum 414 00:19:49,300 --> 00:19:52,710 in between mean value by minus one and nums. 415 00:19:52,780 --> 00:19:52,970 OK. 416 00:19:53,610 --> 00:19:53,880 Right. 417 00:19:54,150 --> 00:19:54,510 Perfect. 418 00:19:54,900 --> 00:20:02,610 Now we have this means that it's time to write our made for loop and I am iterating from the last element 419 00:20:02,640 --> 00:20:07,440 which here is at minus one all the way to position one. 420 00:20:07,680 --> 00:20:07,900 Right. 421 00:20:07,920 --> 00:20:09,150 Because James the second one. 422 00:20:09,180 --> 00:20:13,110 So I can go to position zero and J minus minus. 423 00:20:13,230 --> 00:20:14,310 So I know the J. 424 00:20:14,580 --> 00:20:20,100 Now I know the value of A.I. because A.I. is always going to be mean van of J. 425 00:20:20,100 --> 00:20:20,620 Minus one. 426 00:20:21,360 --> 00:20:25,020 And I shall find my most favorable. 427 00:20:25,800 --> 00:20:27,070 Which I will find it in the stack. 428 00:20:27,180 --> 00:20:29,590 But first of all, steak is not increasingly. 429 00:20:30,090 --> 00:20:31,830 I need to push these elements right. 430 00:20:32,040 --> 00:20:35,580 Each element of the array will be inserted to the steak at some point. 431 00:20:35,880 --> 00:20:37,740 So I need to be certain of this element. 432 00:20:37,800 --> 00:20:43,200 But in order to keep it non increasingly sorted, I need to pop those elements from the stack which 433 00:20:43,200 --> 00:20:44,490 are less than me. 434 00:20:44,880 --> 00:20:47,280 So while the steak is not empty. 435 00:20:47,640 --> 00:20:49,770 So not steak that empty. 436 00:20:50,880 --> 00:20:53,940 And I will go to steak that Bob. 437 00:20:54,660 --> 00:20:57,500 Remember, here I have positions, not values. 438 00:20:57,870 --> 00:21:01,830 So for the value, I shall look at nums of stacked up top. 439 00:21:02,610 --> 00:21:07,890 And while this value is hope is less than my value. 440 00:21:08,220 --> 00:21:10,050 Nums of G. 441 00:21:10,440 --> 00:21:10,710 Right. 442 00:21:11,280 --> 00:21:11,970 What should I do? 443 00:21:12,390 --> 00:21:13,170 Well, first of all. 444 00:21:14,170 --> 00:21:15,670 This could be a possible key. 445 00:21:17,240 --> 00:21:20,900 So I shall check if nams of those to the top. 446 00:21:21,560 --> 00:21:25,650 So this aof key is how greater than a of I. 447 00:21:25,840 --> 00:21:26,140 Right. 448 00:21:26,360 --> 00:21:31,610 So if this is greater than my aof I, which I know is mean then of G minus one. 449 00:21:32,330 --> 00:21:32,600 Right. 450 00:21:33,860 --> 00:21:34,240 Perfect. 451 00:21:34,840 --> 00:21:35,830 I returned to write to me. 452 00:21:35,900 --> 00:21:37,010 I have found my solution. 453 00:21:38,080 --> 00:21:39,700 If not, what should I do? 454 00:21:40,510 --> 00:21:42,670 I remove that position from my stick. 455 00:21:43,270 --> 00:21:43,690 Perfect. 456 00:21:43,730 --> 00:21:44,500 Not after this. 457 00:21:44,500 --> 00:21:48,330 When it finishes execution, I will insert my element in my state. 458 00:21:48,640 --> 00:21:49,850 So stick that push. 459 00:21:50,410 --> 00:21:51,910 Remember, those are positions. 460 00:21:51,910 --> 00:21:53,240 So I insert here, Jake. 461 00:21:53,590 --> 00:21:55,140 Not a not none of G. 462 00:21:55,270 --> 00:21:55,540 Right. 463 00:21:56,050 --> 00:22:00,550 So I have basically I have basically all that I need. 464 00:22:01,630 --> 00:22:07,090 So after this for loop finishes execution, let me fall right here. 465 00:22:07,600 --> 00:22:08,580 I should just return false. 466 00:22:08,920 --> 00:22:09,190 Right. 467 00:22:09,760 --> 00:22:11,980 So fix the second element, which is J. 468 00:22:12,580 --> 00:22:17,590 We know what's the first element and we try it from the stake of the possible fourth element in the 469 00:22:17,590 --> 00:22:17,770 end. 470 00:22:17,860 --> 00:22:18,700 We just return false. 471 00:22:18,850 --> 00:22:19,240 And that's it. 472 00:22:19,810 --> 00:22:20,890 Let's run the code. 473 00:22:21,250 --> 00:22:21,850 Fingers crossed. 474 00:22:23,890 --> 00:22:25,090 Ron Paul, the result? 475 00:22:25,240 --> 00:22:25,690 Let's see. 476 00:22:29,800 --> 00:22:30,120 All right. 477 00:22:31,130 --> 00:22:32,300 Passes the test cases. 478 00:22:32,660 --> 00:22:34,430 And now let's submit our solution. 479 00:22:35,150 --> 00:22:35,910 Fingers crossed again. 480 00:22:36,380 --> 00:22:37,760 I've already solved this task. 481 00:22:37,790 --> 00:22:38,600 Two months ago. 482 00:22:39,380 --> 00:22:39,650 All right. 483 00:22:39,680 --> 00:22:40,690 And I have a runtime error. 484 00:22:40,790 --> 00:22:42,350 All this is a corner case. 485 00:22:42,380 --> 00:22:43,140 Be very careful. 486 00:22:44,570 --> 00:22:48,350 In interviews, you will have you will be asked a lot of corner cases. 487 00:22:48,350 --> 00:22:48,620 Right. 488 00:22:48,650 --> 00:22:51,370 So the interviewer will ask you, okay. 489 00:22:51,410 --> 00:22:57,020 Think about some corner cases where you think your algorithm would crash right or won't work, won't 490 00:22:57,020 --> 00:22:58,040 give the right answer. 491 00:22:58,550 --> 00:23:00,260 And you should be very careful on this one. 492 00:23:00,590 --> 00:23:03,080 One of these is always the empty array. 493 00:23:03,290 --> 00:23:03,560 Right. 494 00:23:03,950 --> 00:23:04,520 Very popular. 495 00:23:04,520 --> 00:23:07,010 And it got almost every problem has its corner case. 496 00:23:07,070 --> 00:23:08,690 So how do we check this? 497 00:23:08,720 --> 00:23:10,110 Well, if nonstop, empty. 498 00:23:10,550 --> 00:23:11,690 If this area is empty. 499 00:23:12,140 --> 00:23:13,040 What shall I return? 500 00:23:13,370 --> 00:23:14,060 I return false. 501 00:23:14,090 --> 00:23:14,480 Right away. 502 00:23:14,480 --> 00:23:16,520 Because obviously I won't have a solution. 503 00:23:16,820 --> 00:23:17,980 So let's submit this again. 504 00:23:19,470 --> 00:23:20,330 Fingers crossed again. 505 00:23:21,450 --> 00:23:22,180 Hope for the best. 506 00:23:22,790 --> 00:23:24,210 And we are accepted, right? 507 00:23:24,260 --> 00:23:24,850 Perfect ice. 508 00:23:24,950 --> 00:23:25,880 This was the problem. 509 00:23:26,060 --> 00:23:28,370 First problem that we have solved using the stack. 510 00:23:28,670 --> 00:23:30,080 And there are yet more to come. 511 00:23:30,320 --> 00:23:34,500 And notice how beautiful this is because we had free brute force approaches. 512 00:23:34,580 --> 00:23:34,920 Right. 513 00:23:35,150 --> 00:23:39,080 And cube and square then and again, which is still a brute force approach. 514 00:23:39,380 --> 00:23:42,740 And then getting to the stack in the linear time solution. 515 00:23:42,890 --> 00:23:47,420 Remember, guys, if you really like the content and enjoy seeing me approaching this problems, working 516 00:23:47,420 --> 00:23:51,030 you from my thinking process and writing the code together with me. 517 00:23:51,980 --> 00:23:56,270 Don't forget to really, really support the general hit that subscribe button. 518 00:23:56,420 --> 00:23:57,290 Hit the like button. 519 00:23:57,310 --> 00:24:01,160 Share it with your friends and everyone, which would really find it valuable. 520 00:24:01,220 --> 00:24:03,320 And as always, guys, I will see you in day four. 521 00:24:03,380 --> 00:24:05,090 Keep the hustle and out.