Hello, everyone, and welcome back.
Let's tackle this rotting orange tuti array question together.
So to begin with, there's a bunch of little sub problems that we kind of know exist, but we have not
fully identified yet.
We know what our first step we want to think from a high level what the question is asking us so that
we can determine whether or not we want to begin with a sequential order and then use that sequential
order to do something to set ourselves up so we can solve the remaining problems.
But here, we don't know what those problems are yet.
So let's logically and critically think about the problem and figure out what they are to begin off
with.
There's a couple of things that we know the question wants us to do.
The first is that we want to figure out how many minutes must pass in order for us to convert all of
the fresh oranges into rotting oranges.
Now, the way that these fresh oranges turn into rotting oranges is in a expanding, almost ring like
pattern from the rotting oranges.
So if you were to take this to, for example, we know that from this to we would first rot these oranges
in the first minute and then these oranges in the next minute and then these oranges in the next minute.
And then these ones.
And this one.
So we're always expanding out almost in a pattern that looks like it's level by level by level, if
you want to see it in that kind of way.
In order for us to even start tackling this, we need to also think about one of the major points in
this question that we need to consider.
How many possible rotting oranges are there to begin off with, because in this example, we have only
one rotting orange, but this changes the moment we have more than one.
So let me just modify this so that we have a better idea of what's happening.
If we were to set up another rotting orange here, now we have two points that we need to begin rotting
from.
So in the first minute, this top left two will rot these oranges, but then this one right below this
two is also going to start to rot.
So here we can see that while we are expanding out level by level, it's all happening at once, which
means that we need some way to make sure that when we start figuring out how to rot these oranges in
this level by level pattern every minute.
That we make sure to do it from both of the rotting oranges or all of the rotting oranges at any given
point.
So to begin off with here, we can already get some kind of rough idea that we need to figure out where
all of the rotting oranges are inside of our tutera before we even start.
The other thing to note is also that there is a chance that we might not be able to reach one of these
oranges.
For example, let's imagine that we were to change these oranges.
So let me get rid of these and let's modify this ever so slightly.
If we changed our question like this so that these positions right here are zero, this orange right
here is never going to be reached because technically speaking, we are only taking up down, left and
right.
We cannot reach it diagonally from this nearest orange.
So this orange is always going to stay fresh.
If that's the case, as we know, our question is expecting us to return negative one.
So this means that we also need some way to ensure that once we finish writing as many oranges as possible,
that we are somehow able to determine whether or not there are any fresh oranges left.
Now, at this point, we have not yet figured out what the actual solution and implementation of the
RODDING pattern is going to be.
But we do kind of get the idea that it's a separate problem from the one that we're looking at, which
is how to figure out whether or not there are fresh oranges after we've gotten as many oranges as we
possibly can.
We get this instant because when we think about it, our code is probably going to implement some kind
of traversal.
This much is clear because the nature of how we start from oranges and then start moving out in a immediate
pattern of up, right, left down tells us that this is pretty much a rough traversal.
So once we traverse to all the appropriate oranges and we have rotten what we can, our code is going
to end.
It doesn't actually account for how many fresh oranges it was not able to reach.
We know this already about the way that we write reversals so we can tell that figuring out whether
or not after this rotting pattern has happened that there's any fresh oranges left is a separate sub
problem that we need to solve.
So let's solve this first, because it's a smaller problem than solving how to figure out the rodding
pattern.
And here what we can do is we can think about the ways that we can keep track of there being any fresh
oranges.
We can do this in the beginning before we even perform the rodding pattern, or we can do this at the
very end.
We do this at the end because the easiest way is after we've done all of the rodding, we just scan
through the entire two Deira and sequential order and see if there's any fresh oranges left.
If there is, then we know that our rodding pattern couldn't reach that orange.
Therefore, we know that the answer is going to be negative one.
Whereas if we were to do it at the very beginning, what we can do is we can count all of the fresh
oranges that are available before we even do any of the rodding pattern.
Then once we start rotting outwards, whenever we rot and orange, we just decrease the count of fresh
oranges.
And once we're done with our rotting, then we know that if there's any fresh oranges left, if that
count is greater than zero, then there must be fresh oranges that we could not reach.
So we have two perfectly valid solutions, but we don't know which one is better at this point.
But if we start thinking about grouping it with any other such problems that we solved, we might have
a better idea.
Let's think back to the first problem, which is figuring out what the original rodding oranges were
before we even start the rotting pattern.
In order to make sure that we have all of the rotting oranges at the very beginning, what we have to
do is we need to scan through the entire Tuti array and then figure out the positions of all of the
rotting oranges so we know where to begin our rodding pattern.
Once again, we have an implement the pattern yet, but we know that we need to make sure that we check
the entire data structure to find all of the tubes because we're going to scan through the entire 2D
array.
Anyways, in the very beginning, we might as well group that with the fact that we're also counting
all of the fresh oranges.
It's pretty much the exact same sequential traversal.
But now we just split up the logic.
If we see it too, we make sure that we account for the fact that there's a rotting orange here.
If we see a one, we just increase the count of the number of fresh oranges and then we can use that
beginning solution to this problem.
So here we've kind of tackled two different sub problems and we can identify the very least.
That's sequential order is something that we want at the very beginning.
We just want to solve the two problems first.
The first is what are the initial rotting oranges?
And the second is how do we keep track of fresh oranges?
So here I'm just going to say keep track of fresh oranges.
So these are the two problems we need to solve with sequential order.
So here we've identified a starting point with our sequential order, this solves some of our problems,
but not all of our problems.
The main problem left to solve is figuring out how to implement the logic for this rodding order that
we have to do.
So here we know that we want to start rotting outwards in the immediate vicinity of our starting to
oranges, we want to rot outwards into whatever fresh oranges are in the immediate up, right down and
left of any of these rotting oranges and then do the same for the next level of rotting oranges.
The problem is that the order in which we do it has to be tracked in a minute to minute basis.
In some ways you want to see that every ring that we expand outwards from represents a new minute.
And those rings are combined when you group the number of oranges that there are at every level.
If we think about it, we kind of get the instinct that this level by level traversal order is going
to be breadth first search, because as we know with breadth of research, that's exactly the definition.
It picks a starting point and then it starts expanding outwards into the immediate neighbors in these
four directions.
So we know breath research is definitely the right traversal order.
The problem is figuring out how we group it into these minutes appropriately, because when we think
about our breath for a search implementation, we know that we're implementing a Q and a Q. processes
elements one at a time.
It doesn't know whether or not this elements and this elements are at the same level.
So it doesn't know how to implement that break.
And that's where we need to implement it.
This is where we need to get creative.
And this is actually where I want to challenge you to try and think about what to do.
You already know that at the very beginning you have access to the two rodding oranges because we've
already done the sequential order PA.
We've scanned through the entire 2D array.
We know where the two rodding oranges are from here.
We want to start implementing breath for search from the two rodding oranges, but we want to make sure
that we're able to properly track the amount of minutes that are passing whenever a level of orange
is decays and rots away.
So try and figure out a creative solution here, and there's actually multiple ways that you can do
this, we've even done a way already.
If you think back to a binary tree question we did with Breadth First search, there was a point where
we needed to get the level order of a tree.
And the only way we could do so is if we implemented some kind of tracking system that told us when
we were at the start or the end of a level.
I don't know if you remember this question, but if you think back to the solution there, it's very
similar to what we can do here.
Either way, come up with a solution yourself and we can do this together in the next video.