1 00:00:00,780 --> 00:00:01,810 Welcome back, everyone. 2 00:00:02,580 --> 00:00:10,020 So we just tackled how to implement sequential order at the very beginning so that we can get all of 3 00:00:10,020 --> 00:00:15,170 the initial rotten oranges as well as count the total number of fresh oranges. 4 00:00:15,660 --> 00:00:23,040 So using this modified version of our test case, in order to isolate this fresh orange, to demonstrate 5 00:00:23,040 --> 00:00:28,410 and think about the full scope of this question, let's go through this sequential order so that we 6 00:00:28,410 --> 00:00:35,040 can set ourselves up to tackle the rotting breath for a search that we have yet to figure out to begin 7 00:00:35,040 --> 00:00:38,840 with when we do our sequential order or go from left to right, top to down. 8 00:00:39,300 --> 00:00:45,900 So here we identify that there is a rotting orange and then let's start moving to the right and counting 9 00:00:45,900 --> 00:00:46,730 fresh oranges. 10 00:00:47,190 --> 00:00:50,970 So here we see there's one, two, three. 11 00:00:51,720 --> 00:00:54,660 And then we see there's another rotting orange. 12 00:00:55,910 --> 00:01:01,170 So then we continue for five, six, seven, eight, nine. 13 00:01:01,790 --> 00:01:03,920 So we have nine fresh oranges. 14 00:01:05,030 --> 00:01:11,650 Which I'm going to represent as F nine, and we have these two as our starting initial rotting oranges, 15 00:01:12,290 --> 00:01:20,360 so what we need to do is we need to start rotting the oranges outwards from these two positions while 16 00:01:20,360 --> 00:01:27,710 making sure that we know how many minutes of past as we implement our breath for a search and search 17 00:01:27,710 --> 00:01:29,560 outside level by level. 18 00:01:30,410 --> 00:01:33,290 So to begin off with, we know that we need a cue. 19 00:01:34,190 --> 00:01:38,590 The queue is going to tell us which order of elements to process in our breath for a search. 20 00:01:38,630 --> 00:01:42,340 So to begin, we can process these two elements. 21 00:01:43,100 --> 00:01:52,400 So here the first position, we can actually also write it out as zero one two three zero one, two, 22 00:01:52,400 --> 00:01:55,190 three four four the index of these values. 23 00:01:55,910 --> 00:02:00,170 So we know that the very first one here is position zero zero. 24 00:02:00,710 --> 00:02:03,800 And the second one is that position one. 25 00:02:03,800 --> 00:02:05,630 For now. 26 00:02:05,630 --> 00:02:11,660 Before we even continue with our breath for search, let's slow down and think about this a little bit. 27 00:02:12,350 --> 00:02:18,410 At this point, we know that we need to figure out some way to track the number of minutes that have 28 00:02:18,410 --> 00:02:18,980 passed. 29 00:02:19,430 --> 00:02:25,150 And in this case, the minutes represents the current layer that we are working on. 30 00:02:25,490 --> 00:02:33,560 So, for example, at minute zero, we are working on the initial layer, which is the two rotten oranges 31 00:02:33,560 --> 00:02:36,710 that we've initially gotten from here. 32 00:02:36,710 --> 00:02:39,920 What we're doing is we're saying, OK, I want to implement breath for first search. 33 00:02:39,920 --> 00:02:44,300 So starting with this one, I want to take out this first value in our queue. 34 00:02:44,990 --> 00:02:47,060 So the coordinates at zero zero. 35 00:02:47,750 --> 00:02:55,220 And what I want to do is I want to add its immediate neighbors into the queue if it's a fresh orange 36 00:02:55,220 --> 00:02:56,620 and I also want to rot it. 37 00:02:57,170 --> 00:03:00,840 So here the only immediate coordinate that is a fresh orange is below it. 38 00:03:01,670 --> 00:03:07,580 Now what you'll notice is that the moment we add these coordinates into our queue, we see that our 39 00:03:07,580 --> 00:03:15,590 queue has no idea that once it processes the next value, which is this one for that we have reached 40 00:03:15,590 --> 00:03:17,330 the end of the level. 41 00:03:17,600 --> 00:03:23,300 What I mean by this is that once we've processed this too, and we've taken the only fresh orange that's 42 00:03:23,300 --> 00:03:25,330 under it and we added to our queue again. 43 00:03:25,520 --> 00:03:28,550 So this one is at the coordinates of two four. 44 00:03:30,170 --> 00:03:36,080 Here, technically speaking, we've done everything we need to do with the two oranges, theoretically 45 00:03:36,080 --> 00:03:38,840 speaking, we need to increment our minutes by one. 46 00:03:39,080 --> 00:03:47,300 But how are we able to introduce this logic if our cue has no idea that it has processed the two elements 47 00:03:47,300 --> 00:03:49,240 that were in the previous layer? 48 00:03:50,090 --> 00:03:57,080 We have to implement some kind of tracker that will tell our cue that at this point the minutes should 49 00:03:57,080 --> 00:03:59,510 probably increment, or at least it should tell our code. 50 00:03:59,510 --> 00:04:02,770 It doesn't need to tell the cue, but we need to implement some kind of system here. 51 00:04:03,290 --> 00:04:07,190 So let's backtrack a little bit before when we had just our initial values. 52 00:04:07,880 --> 00:04:13,910 And what we can do is a very similar solution to what we had with the level or implementation and a 53 00:04:13,910 --> 00:04:17,390 binary tree, which was also doing breadth first search with a cube. 54 00:04:17,900 --> 00:04:21,140 We want to instantiate some kind of value called queue length. 55 00:04:21,800 --> 00:04:26,690 This queue length at this point is going to initialize for the value that the queue is currently. 56 00:04:26,690 --> 00:04:27,410 So it's two. 57 00:04:27,920 --> 00:04:33,110 So we know that this length value has two values in it inside of the queue. 58 00:04:33,110 --> 00:04:39,740 And the moment that we've processed two elements, we have reached the end of this current processing 59 00:04:39,740 --> 00:04:42,520 level and therefore the minutes can increment. 60 00:04:43,190 --> 00:04:49,610 So once we start, what we'll see is that two is going to pop out of our queue. 61 00:04:50,300 --> 00:04:53,720 And once we pop it out, we're also going to drop the count of the length by one. 62 00:04:54,380 --> 00:04:57,630 So the value that we're working with is at zero zero. 63 00:04:58,370 --> 00:05:02,780 Now, let's think about the logic that we want to apply when we have this rotting orange. 64 00:05:03,290 --> 00:05:06,680 We want to be rotting in the immediate vicinity of our breath for search. 65 00:05:06,680 --> 00:05:10,550 So we take the immediate top right, down, left, and look for any fresh oranges. 66 00:05:11,000 --> 00:05:13,780 We see right here that there's a fresh orange to the bottom. 67 00:05:14,060 --> 00:05:18,350 So first we are going to rot that value, switching it from a one to two. 68 00:05:19,100 --> 00:05:24,740 We're going to decrease the number of fresh oranges that we have because now we've reduced the number 69 00:05:24,740 --> 00:05:25,910 of fresh oranges by one. 70 00:05:26,570 --> 00:05:32,810 But we are also going to add the coordinates of this value into a queue so that we can process it in 71 00:05:32,810 --> 00:05:35,450 a later part of our breath for research. 72 00:05:35,870 --> 00:05:37,700 So here I just add one zero in. 73 00:05:38,420 --> 00:05:41,290 And now is there anything left that we need to do with this value? 74 00:05:41,630 --> 00:05:42,830 Now we're done with the logic. 75 00:05:42,830 --> 00:05:44,420 We can continue our process. 76 00:05:45,380 --> 00:05:51,290 So the next thing we do is we take the next value one, for we once again decrease our queue length. 77 00:05:52,790 --> 00:05:58,430 And now we're out one four and we're going to walk through the same logic that we did for our previous 78 00:05:58,430 --> 00:05:59,130 rotten orange. 79 00:05:59,810 --> 00:06:04,460 So here from this value, we check the media up, right, down, left, and see there's a fresh orange 80 00:06:04,460 --> 00:06:04,910 below it. 81 00:06:05,120 --> 00:06:07,430 So we are going to rot that value. 82 00:06:08,850 --> 00:06:15,480 And we are also going to decrease our fresh oranges by one, then we are going to take the coordinates 83 00:06:15,480 --> 00:06:18,000 here at two four and add it to our Q. 84 00:06:20,320 --> 00:06:26,350 So now we finished with the logic that we need to apply to this rotten orange, but now we notice that 85 00:06:26,350 --> 00:06:31,750 our queue length is at zero, which means that we finish processing all of the oranges at this first 86 00:06:31,750 --> 00:06:32,530 layer level. 87 00:06:33,220 --> 00:06:39,280 Once we've done this, we know that the moment our queue length hits zero all of the next values to 88 00:06:39,280 --> 00:06:40,740 process on the next level. 89 00:06:40,960 --> 00:06:42,070 So we want to do two things. 90 00:06:42,070 --> 00:06:45,990 The first is we know that we're done with this current level. 91 00:06:46,000 --> 00:06:48,010 So one minute has passed. 92 00:06:48,280 --> 00:06:52,070 The next is that we have to re instantiate our queue length. 93 00:06:52,570 --> 00:06:54,340 So how many values are there in our queue? 94 00:06:54,370 --> 00:06:55,120 There's two. 95 00:06:55,300 --> 00:07:02,320 We can just sacu length to two and now we just repeat this process again, except the next level is 96 00:07:02,320 --> 00:07:04,300 going to be at this layer. 97 00:07:05,290 --> 00:07:11,860 So here we can see that we have some kind of repeatable pattern that allows us to make sure that at 98 00:07:11,860 --> 00:07:16,690 every level of our breadth of research, we can keep track of the number of minutes that have passed 99 00:07:16,690 --> 00:07:19,280 by the level using this queue length value. 100 00:07:20,110 --> 00:07:23,050 So if you want to try and walk through this yourself, you can do so. 101 00:07:23,260 --> 00:07:24,940 I'm going to do it right now. 102 00:07:25,660 --> 00:07:28,200 So let's just continue and finish this question. 103 00:07:29,360 --> 00:07:36,800 Here, I just want to shift these values up to make sure that we have space, so we had one zero and 104 00:07:36,800 --> 00:07:37,670 two for. 105 00:07:39,190 --> 00:07:43,420 And as we continue, we pop out the first value and drop our queue length. 106 00:07:44,760 --> 00:07:46,710 So we're looking at one zero. 107 00:07:50,310 --> 00:07:55,380 So here we take this value, we look in its immediate vicinity, we see there's a fresh orange to the 108 00:07:55,380 --> 00:07:55,710 right. 109 00:07:56,590 --> 00:07:59,590 This is one one, so we want to write it. 110 00:08:00,900 --> 00:08:02,280 Decrease the fresh count. 111 00:08:04,290 --> 00:08:08,910 And we also now want to add its coordinates into our Q So one one. 112 00:08:11,610 --> 00:08:15,660 Then we're done with this value, we continue, we take the next one to four. 113 00:08:18,920 --> 00:08:20,540 We've got to decrease our queue length. 114 00:08:21,450 --> 00:08:27,180 And now at two four, we go up, right, down, left, there's two fresh oranges, so we want to rock 115 00:08:27,180 --> 00:08:28,200 both these values. 116 00:08:30,400 --> 00:08:33,220 Which means that we're going to drop our fresh count by two. 117 00:08:35,620 --> 00:08:41,320 This also means we need to add both of these coordinates in the order of up, right, down, left into 118 00:08:41,350 --> 00:08:44,560 our cube, so we're going to do down first at three, four. 119 00:08:47,560 --> 00:08:50,980 And then we're going to do the next value add two, three. 120 00:08:56,220 --> 00:09:01,740 So now that we're done with you for what we can see is that our queue length hits zero, we're finished 121 00:09:01,740 --> 00:09:05,880 with this level, we can now increment our minutes by one. 122 00:09:06,850 --> 00:09:12,280 So let's continue with the rest of our queue, so I'm just going to actually extend the queue instead 123 00:09:12,280 --> 00:09:15,550 of constantly shifting the values and hopefully that's enough space. 124 00:09:16,430 --> 00:09:20,930 And now, before we begin, we have to re instantiate our queue length, so here there's three values 125 00:09:20,930 --> 00:09:23,330 in our queue, so queue length becomes three. 126 00:09:24,870 --> 00:09:29,790 And we're going to pop out the first value in our queue, which is one one, and we're also going to 127 00:09:29,790 --> 00:09:30,950 decrease the queue length. 128 00:09:32,130 --> 00:09:37,430 So here one one is this orange and we check its immediate vicinity. 129 00:09:37,470 --> 00:09:38,900 We see there's one right here. 130 00:09:39,240 --> 00:09:40,940 So we are going to rot this value. 131 00:09:41,760 --> 00:09:44,280 We're going to decrease our fresh count to three. 132 00:09:45,740 --> 00:09:51,020 And now when we look at this continent, we want to add it at two, one, two, ArcView. 133 00:09:54,440 --> 00:10:00,530 So now we want to move on to the next value, because we're done with this rotting orange, we take 134 00:10:00,530 --> 00:10:03,020 three, four, we drop our queue length. 135 00:10:05,130 --> 00:10:10,320 We do the same logic here, we look in its immediate vicinity, up, right, down, left, there's no 136 00:10:10,320 --> 00:10:11,950 oranges, so there's nothing to change. 137 00:10:12,690 --> 00:10:17,700 All we know is that we have finished processing this value and we can move on to the last value. 138 00:10:17,700 --> 00:10:19,410 So we take out two, three right here. 139 00:10:19,710 --> 00:10:21,240 We decrease our queue length. 140 00:10:27,510 --> 00:10:32,990 And now we took up right, down, left, there's one fresh one to the left, right here. 141 00:10:33,030 --> 00:10:34,380 So let's rock this value. 142 00:10:36,660 --> 00:10:38,790 Let's decrease our fresh orange count. 143 00:10:41,200 --> 00:10:47,740 And what we're going to say is that at this point now, right here, let's add this value to three or 144 00:10:47,740 --> 00:10:50,800 two to actually into our Q. 145 00:10:53,040 --> 00:10:57,330 And now we see that link, the zero minutes increments to three. 146 00:10:58,260 --> 00:11:01,210 And we are now going to reinstitute the queue length. 147 00:11:01,620 --> 00:11:03,000 There's two values in here. 148 00:11:04,730 --> 00:11:09,380 And I'm going to unfortunately have to shift these values up again because I've ran out of space, so 149 00:11:09,380 --> 00:11:12,410 we had to one and two to. 150 00:11:14,890 --> 00:11:18,370 So let's pop out the first value, we're going to drop our queue length. 151 00:11:19,430 --> 00:11:20,750 We're working with two one. 152 00:11:24,030 --> 00:11:29,610 So at two one right here, what we see is that up, right, down, left, down, right here, there 153 00:11:29,610 --> 00:11:30,870 is a value that we want. 154 00:11:31,620 --> 00:11:32,550 It's a fresh orange. 155 00:11:32,550 --> 00:11:33,660 So we write it first. 156 00:11:34,140 --> 00:11:35,790 We drop our fresh count. 157 00:11:37,870 --> 00:11:41,410 And now we take its coordinates at three one. 158 00:11:44,480 --> 00:11:52,190 We finished what we need to do with two one, we want to shift up the next value, add two two, we 159 00:11:52,190 --> 00:11:54,050 drop our queue length count. 160 00:11:55,180 --> 00:12:00,010 And what we notice is that there's no immediate fresh oranges in its vicinity, so there's nothing left 161 00:12:00,010 --> 00:12:00,580 to do here. 162 00:12:01,000 --> 00:12:03,550 We see that we've reached the end of our queue length. 163 00:12:04,060 --> 00:12:07,030 So right here we want to increase our minutes once again. 164 00:12:08,640 --> 00:12:12,780 And then we can continue MPRI process the values, queue length is now at one. 165 00:12:14,790 --> 00:12:19,350 By here, what we're going to see is that once we pop this value out, we're going to drop queue length 166 00:12:19,350 --> 00:12:21,880 again and walk like this at zero. 167 00:12:21,900 --> 00:12:24,540 There's no more fresh oranges to process. 168 00:12:24,550 --> 00:12:25,820 So technically, we're done. 169 00:12:25,830 --> 00:12:27,990 There's actually no need to increase the minutes. 170 00:12:28,410 --> 00:12:34,650 So we need to make sure that when we code this out that we don't count for the very last level of rotten 171 00:12:34,650 --> 00:12:39,540 oranges inside of the queue of our breath research, because while our code is going to add them in, 172 00:12:39,720 --> 00:12:41,670 we don't want to change our minutes anymore. 173 00:12:42,760 --> 00:12:47,950 After this is done and we finish processing all of the values inside of our queue, now we have our 174 00:12:47,950 --> 00:12:49,540 total minutes at the end. 175 00:12:50,170 --> 00:12:56,710 This would normally work as the answer, but we noticed that our fresh orange count still has a value 176 00:12:56,710 --> 00:12:57,690 that's greater than zero. 177 00:12:57,700 --> 00:13:02,770 There's one which is clearly indicated by this fresh orange that we were never able to reach. 178 00:13:03,190 --> 00:13:08,050 So if the fresh orange value is greater than zero, instead we return negative one. 179 00:13:08,740 --> 00:13:14,380 If this value is instead equal to zero, then we just return the minutes and now we have an answer. 180 00:13:15,370 --> 00:13:21,490 So here you can see how we were able to slowly piece this together by thinking about the problem and 181 00:13:21,490 --> 00:13:26,920 breaking out the small some problems, first we need to think, how do we make sure that we get all 182 00:13:26,920 --> 00:13:28,690 of the rotten oranges before we begin? 183 00:13:29,530 --> 00:13:34,660 How do we count the total number of fresh oranges so that we know that by the time we finish going through 184 00:13:34,660 --> 00:13:39,970 this breath for a search traversal of rotting the oranges, that if there's any values left, then we 185 00:13:39,970 --> 00:13:45,760 have to make sure that we know that we can return negative one, because if there's any fresher oranges 186 00:13:45,760 --> 00:13:48,310 left, then they means they could never be reached. 187 00:13:48,640 --> 00:13:52,960 Then it was a matter of figuring out the logic of implementing this breath for a search solution with 188 00:13:52,960 --> 00:13:57,100 this queue length to tell us which level of the rotting order we're at. 189 00:13:58,000 --> 00:14:00,400 So this I want you to try and cut it out yourself. 190 00:14:00,730 --> 00:14:05,800 There's going to be a little bit of tricks here about thinking of some edge cases when you're actually 191 00:14:05,800 --> 00:14:06,520 cutting this up. 192 00:14:06,700 --> 00:14:11,680 For example, in order for this queue length solution to work, you have to account for situations where 193 00:14:11,680 --> 00:14:15,240 the grid is only one size and maybe it looks something like this. 194 00:14:16,330 --> 00:14:21,020 So make sure that you test your code properly and think about these conditions as well as the normal 195 00:14:21,040 --> 00:14:24,010 cases that we have and make sure your solution works. 196 00:14:24,400 --> 00:14:26,920 So I'll show you how to write that code in the next lesson.