Welcome back, everyone.
So we just tackled how to implement sequential order at the very beginning so that we can get all of
the initial rotten oranges as well as count the total number of fresh oranges.
So using this modified version of our test case, in order to isolate this fresh orange, to demonstrate
and think about the full scope of this question, let's go through this sequential order so that we
can set ourselves up to tackle the rotting breath for a search that we have yet to figure out to begin
with when we do our sequential order or go from left to right, top to down.
So here we identify that there is a rotting orange and then let's start moving to the right and counting
fresh oranges.
So here we see there's one, two, three.
And then we see there's another rotting orange.
So then we continue for five, six, seven, eight, nine.
So we have nine fresh oranges.
Which I'm going to represent as F nine, and we have these two as our starting initial rotting oranges,
so what we need to do is we need to start rotting the oranges outwards from these two positions while
making sure that we know how many minutes of past as we implement our breath for a search and search
outside level by level.
So to begin off with, we know that we need a cue.
The queue is going to tell us which order of elements to process in our breath for a search.
So to begin, we can process these two elements.
So here the first position, we can actually also write it out as zero one two three zero one, two,
three four four the index of these values.
So we know that the very first one here is position zero zero.
And the second one is that position one.
For now.
Before we even continue with our breath for search, let's slow down and think about this a little bit.
At this point, we know that we need to figure out some way to track the number of minutes that have
passed.
And in this case, the minutes represents the current layer that we are working on.
So, for example, at minute zero, we are working on the initial layer, which is the two rotten oranges
that we've initially gotten from here.
What we're doing is we're saying, OK, I want to implement breath for first search.
So starting with this one, I want to take out this first value in our queue.
So the coordinates at zero zero.
And what I want to do is I want to add its immediate neighbors into the queue if it's a fresh orange
and I also want to rot it.
So here the only immediate coordinate that is a fresh orange is below it.
Now what you'll notice is that the moment we add these coordinates into our queue, we see that our
queue has no idea that once it processes the next value, which is this one for that we have reached
the end of the level.
What I mean by this is that once we've processed this too, and we've taken the only fresh orange that's
under it and we added to our queue again.
So this one is at the coordinates of two four.
Here, technically speaking, we've done everything we need to do with the two oranges, theoretically
speaking, we need to increment our minutes by one.
But how are we able to introduce this logic if our cue has no idea that it has processed the two elements
that were in the previous layer?
We have to implement some kind of tracker that will tell our cue that at this point the minutes should
probably increment, or at least it should tell our code.
It doesn't need to tell the cue, but we need to implement some kind of system here.
So let's backtrack a little bit before when we had just our initial values.
And what we can do is a very similar solution to what we had with the level or implementation and a
binary tree, which was also doing breadth first search with a cube.
We want to instantiate some kind of value called queue length.
This queue length at this point is going to initialize for the value that the queue is currently.
So it's two.
So we know that this length value has two values in it inside of the queue.
And the moment that we've processed two elements, we have reached the end of this current processing
level and therefore the minutes can increment.
So once we start, what we'll see is that two is going to pop out of our queue.
And once we pop it out, we're also going to drop the count of the length by one.
So the value that we're working with is at zero zero.
Now, let's think about the logic that we want to apply when we have this rotting orange.
We want to be rotting in the immediate vicinity of our breath for search.
So we take the immediate top right, down, left, and look for any fresh oranges.
We see right here that there's a fresh orange to the bottom.
So first we are going to rot that value, switching it from a one to two.
We're going to decrease the number of fresh oranges that we have because now we've reduced the number
of fresh oranges by one.
But we are also going to add the coordinates of this value into a queue so that we can process it in
a later part of our breath for research.
So here I just add one zero in.
And now is there anything left that we need to do with this value?
Now we're done with the logic.
We can continue our process.
So the next thing we do is we take the next value one, for we once again decrease our queue length.
And now we're out one four and we're going to walk through the same logic that we did for our previous
rotten orange.
So here from this value, we check the media up, right, down, left, and see there's a fresh orange
below it.
So we are going to rot that value.
And we are also going to decrease our fresh oranges by one, then we are going to take the coordinates
here at two four and add it to our Q.
So now we finished with the logic that we need to apply to this rotten orange, but now we notice that
our queue length is at zero, which means that we finish processing all of the oranges at this first
layer level.
Once we've done this, we know that the moment our queue length hits zero all of the next values to
process on the next level.
So we want to do two things.
The first is we know that we're done with this current level.
So one minute has passed.
The next is that we have to re instantiate our queue length.
So how many values are there in our queue?
There's two.
We can just sacu length to two and now we just repeat this process again, except the next level is
going to be at this layer.
So here we can see that we have some kind of repeatable pattern that allows us to make sure that at
every level of our breadth of research, we can keep track of the number of minutes that have passed
by the level using this queue length value.
So if you want to try and walk through this yourself, you can do so.
I'm going to do it right now.
So let's just continue and finish this question.
Here, I just want to shift these values up to make sure that we have space, so we had one zero and
two for.
And as we continue, we pop out the first value and drop our queue length.
So we're looking at one zero.
So here we take this value, we look in its immediate vicinity, we see there's a fresh orange to the
right.
This is one one, so we want to write it.
Decrease the fresh count.
And we also now want to add its coordinates into our Q So one one.
Then we're done with this value, we continue, we take the next one to four.
We've got to decrease our queue length.
And now at two four, we go up, right, down, left, there's two fresh oranges, so we want to rock
both these values.
Which means that we're going to drop our fresh count by two.
This also means we need to add both of these coordinates in the order of up, right, down, left into
our cube, so we're going to do down first at three, four.
And then we're going to do the next value add two, three.
So now that we're done with you for what we can see is that our queue length hits zero, we're finished
with this level, we can now increment our minutes by one.
So let's continue with the rest of our queue, so I'm just going to actually extend the queue instead
of constantly shifting the values and hopefully that's enough space.
And now, before we begin, we have to re instantiate our queue length, so here there's three values
in our queue, so queue length becomes three.
And we're going to pop out the first value in our queue, which is one one, and we're also going to
decrease the queue length.
So here one one is this orange and we check its immediate vicinity.
We see there's one right here.
So we are going to rot this value.
We're going to decrease our fresh count to three.
And now when we look at this continent, we want to add it at two, one, two, ArcView.
So now we want to move on to the next value, because we're done with this rotting orange, we take
three, four, we drop our queue length.
We do the same logic here, we look in its immediate vicinity, up, right, down, left, there's no
oranges, so there's nothing to change.
All we know is that we have finished processing this value and we can move on to the last value.
So we take out two, three right here.
We decrease our queue length.
And now we took up right, down, left, there's one fresh one to the left, right here.
So let's rock this value.
Let's decrease our fresh orange count.
And what we're going to say is that at this point now, right here, let's add this value to three or
two to actually into our Q.
And now we see that link, the zero minutes increments to three.
And we are now going to reinstitute the queue length.
There's two values in here.
And I'm going to unfortunately have to shift these values up again because I've ran out of space, so
we had to one and two to.
So let's pop out the first value, we're going to drop our queue length.
We're working with two one.
So at two one right here, what we see is that up, right, down, left, down, right here, there
is a value that we want.
It's a fresh orange.
So we write it first.
We drop our fresh count.
And now we take its coordinates at three one.
We finished what we need to do with two one, we want to shift up the next value, add two two, we
drop our queue length count.
And what we notice is that there's no immediate fresh oranges in its vicinity, so there's nothing left
to do here.
We see that we've reached the end of our queue length.
So right here we want to increase our minutes once again.
And then we can continue MPRI process the values, queue length is now at one.
By here, what we're going to see is that once we pop this value out, we're going to drop queue length
again and walk like this at zero.
There's no more fresh oranges to process.
So technically, we're done.
There's actually no need to increase the minutes.
So we need to make sure that when we code this out that we don't count for the very last level of rotten
oranges inside of the queue of our breath research, because while our code is going to add them in,
we don't want to change our minutes anymore.
After this is done and we finish processing all of the values inside of our queue, now we have our
total minutes at the end.
This would normally work as the answer, but we noticed that our fresh orange count still has a value
that's greater than zero.
There's one which is clearly indicated by this fresh orange that we were never able to reach.
So if the fresh orange value is greater than zero, instead we return negative one.
If this value is instead equal to zero, then we just return the minutes and now we have an answer.
So here you can see how we were able to slowly piece this together by thinking about the problem and
breaking out the small some problems, first we need to think, how do we make sure that we get all
of the rotten oranges before we begin?
How do we count the total number of fresh oranges so that we know that by the time we finish going through
this breath for a search traversal of rotting the oranges, that if there's any values left, then we
have to make sure that we know that we can return negative one, because if there's any fresher oranges
left, then they means they could never be reached.
Then it was a matter of figuring out the logic of implementing this breath for a search solution with
this queue length to tell us which level of the rotting order we're at.
So this I want you to try and cut it out yourself.
There's going to be a little bit of tricks here about thinking of some edge cases when you're actually
cutting this up.
For example, in order for this queue length solution to work, you have to account for situations where
the grid is only one size and maybe it looks something like this.
So make sure that you test your code properly and think about these conditions as well as the normal
cases that we have and make sure your solution works.
So I'll show you how to write that code in the next lesson.