1
00:00:00,420 --> 00:00:02,160
Hello, everyone, and welcome back.

2
00:00:02,730 --> 00:00:06,680
Let's tackle this rotting orange tuti array question together.

3
00:00:07,350 --> 00:00:13,080
So to begin with, there's a bunch of little sub problems that we kind of know exist, but we have not

4
00:00:13,080 --> 00:00:14,610
fully identified yet.

5
00:00:15,090 --> 00:00:20,160
We know what our first step we want to think from a high level what the question is asking us so that

6
00:00:20,160 --> 00:00:25,470
we can determine whether or not we want to begin with a sequential order and then use that sequential

7
00:00:25,470 --> 00:00:30,930
order to do something to set ourselves up so we can solve the remaining problems.

8
00:00:31,380 --> 00:00:33,360
But here, we don't know what those problems are yet.

9
00:00:33,360 --> 00:00:40,020
So let's logically and critically think about the problem and figure out what they are to begin off

10
00:00:40,020 --> 00:00:40,380
with.

11
00:00:40,620 --> 00:00:43,890
There's a couple of things that we know the question wants us to do.

12
00:00:44,280 --> 00:00:50,550
The first is that we want to figure out how many minutes must pass in order for us to convert all of

13
00:00:50,550 --> 00:00:53,590
the fresh oranges into rotting oranges.

14
00:00:54,000 --> 00:01:01,110
Now, the way that these fresh oranges turn into rotting oranges is in a expanding, almost ring like

15
00:01:01,110 --> 00:01:03,270
pattern from the rotting oranges.

16
00:01:03,450 --> 00:01:10,950
So if you were to take this to, for example, we know that from this to we would first rot these oranges

17
00:01:10,950 --> 00:01:16,800
in the first minute and then these oranges in the next minute and then these oranges in the next minute.

18
00:01:17,040 --> 00:01:18,090
And then these ones.

19
00:01:18,090 --> 00:01:18,840
And this one.

20
00:01:18,840 --> 00:01:19,470
And this one.

21
00:01:19,470 --> 00:01:20,160
And this one.

22
00:01:20,610 --> 00:01:28,410
So we're always expanding out almost in a pattern that looks like it's level by level by level, if

23
00:01:28,410 --> 00:01:30,570
you want to see it in that kind of way.

24
00:01:31,390 --> 00:01:38,290
In order for us to even start tackling this, we need to also think about one of the major points in

25
00:01:38,290 --> 00:01:40,120
this question that we need to consider.

26
00:01:41,240 --> 00:01:47,330
How many possible rotting oranges are there to begin off with, because in this example, we have only

27
00:01:47,330 --> 00:01:52,400
one rotting orange, but this changes the moment we have more than one.

28
00:01:52,640 --> 00:01:56,480
So let me just modify this so that we have a better idea of what's happening.

29
00:01:57,490 --> 00:02:05,080
If we were to set up another rotting orange here, now we have two points that we need to begin rotting

30
00:02:05,080 --> 00:02:05,530
from.

31
00:02:06,160 --> 00:02:13,150
So in the first minute, this top left two will rot these oranges, but then this one right below this

32
00:02:13,150 --> 00:02:15,480
two is also going to start to rot.

33
00:02:16,360 --> 00:02:23,890
So here we can see that while we are expanding out level by level, it's all happening at once, which

34
00:02:23,890 --> 00:02:31,180
means that we need some way to make sure that when we start figuring out how to rot these oranges in

35
00:02:31,180 --> 00:02:33,970
this level by level pattern every minute.

36
00:02:34,810 --> 00:02:41,050
That we make sure to do it from both of the rotting oranges or all of the rotting oranges at any given

37
00:02:41,050 --> 00:02:41,480
point.

38
00:02:42,340 --> 00:02:48,790
So to begin off with here, we can already get some kind of rough idea that we need to figure out where

39
00:02:48,820 --> 00:02:54,290
all of the rotting oranges are inside of our tutera before we even start.

40
00:02:54,940 --> 00:03:00,850
The other thing to note is also that there is a chance that we might not be able to reach one of these

41
00:03:00,850 --> 00:03:01,450
oranges.

42
00:03:01,720 --> 00:03:07,300
For example, let's imagine that we were to change these oranges.

43
00:03:07,330 --> 00:03:11,830
So let me get rid of these and let's modify this ever so slightly.

44
00:03:12,790 --> 00:03:20,440
If we changed our question like this so that these positions right here are zero, this orange right

45
00:03:20,440 --> 00:03:28,300
here is never going to be reached because technically speaking, we are only taking up down, left and

46
00:03:28,300 --> 00:03:28,570
right.

47
00:03:28,580 --> 00:03:32,100
We cannot reach it diagonally from this nearest orange.

48
00:03:32,470 --> 00:03:35,680
So this orange is always going to stay fresh.

49
00:03:36,220 --> 00:03:40,630
If that's the case, as we know, our question is expecting us to return negative one.

50
00:03:41,170 --> 00:03:49,210
So this means that we also need some way to ensure that once we finish writing as many oranges as possible,

51
00:03:49,210 --> 00:03:55,080
that we are somehow able to determine whether or not there are any fresh oranges left.

52
00:03:55,630 --> 00:04:02,380
Now, at this point, we have not yet figured out what the actual solution and implementation of the

53
00:04:02,380 --> 00:04:04,420
RODDING pattern is going to be.

54
00:04:04,660 --> 00:04:10,300
But we do kind of get the idea that it's a separate problem from the one that we're looking at, which

55
00:04:10,300 --> 00:04:16,240
is how to figure out whether or not there are fresh oranges after we've gotten as many oranges as we

56
00:04:16,240 --> 00:04:17,040
possibly can.

57
00:04:17,560 --> 00:04:24,010
We get this instant because when we think about it, our code is probably going to implement some kind

58
00:04:24,010 --> 00:04:24,670
of traversal.

59
00:04:25,240 --> 00:04:32,710
This much is clear because the nature of how we start from oranges and then start moving out in a immediate

60
00:04:32,710 --> 00:04:37,870
pattern of up, right, left down tells us that this is pretty much a rough traversal.

61
00:04:38,560 --> 00:04:45,310
So once we traverse to all the appropriate oranges and we have rotten what we can, our code is going

62
00:04:45,310 --> 00:04:45,880
to end.

63
00:04:46,330 --> 00:04:51,510
It doesn't actually account for how many fresh oranges it was not able to reach.

64
00:04:52,000 --> 00:04:58,360
We know this already about the way that we write reversals so we can tell that figuring out whether

65
00:04:58,360 --> 00:05:04,090
or not after this rotting pattern has happened that there's any fresh oranges left is a separate sub

66
00:05:04,090 --> 00:05:05,290
problem that we need to solve.

67
00:05:05,710 --> 00:05:10,480
So let's solve this first, because it's a smaller problem than solving how to figure out the rodding

68
00:05:10,480 --> 00:05:11,050
pattern.

69
00:05:11,740 --> 00:05:18,580
And here what we can do is we can think about the ways that we can keep track of there being any fresh

70
00:05:18,580 --> 00:05:19,000
oranges.

71
00:05:19,480 --> 00:05:24,640
We can do this in the beginning before we even perform the rodding pattern, or we can do this at the

72
00:05:24,640 --> 00:05:25,420
very end.

73
00:05:26,230 --> 00:05:31,630
We do this at the end because the easiest way is after we've done all of the rodding, we just scan

74
00:05:31,630 --> 00:05:36,790
through the entire two Deira and sequential order and see if there's any fresh oranges left.

75
00:05:36,970 --> 00:05:41,410
If there is, then we know that our rodding pattern couldn't reach that orange.

76
00:05:41,440 --> 00:05:45,220
Therefore, we know that the answer is going to be negative one.

77
00:05:46,000 --> 00:05:50,890
Whereas if we were to do it at the very beginning, what we can do is we can count all of the fresh

78
00:05:50,890 --> 00:05:55,720
oranges that are available before we even do any of the rodding pattern.

79
00:05:56,470 --> 00:06:03,160
Then once we start rotting outwards, whenever we rot and orange, we just decrease the count of fresh

80
00:06:03,160 --> 00:06:03,730
oranges.

81
00:06:03,940 --> 00:06:09,970
And once we're done with our rotting, then we know that if there's any fresh oranges left, if that

82
00:06:09,970 --> 00:06:15,220
count is greater than zero, then there must be fresh oranges that we could not reach.

83
00:06:15,610 --> 00:06:21,100
So we have two perfectly valid solutions, but we don't know which one is better at this point.

84
00:06:21,490 --> 00:06:26,620
But if we start thinking about grouping it with any other such problems that we solved, we might have

85
00:06:26,620 --> 00:06:27,520
a better idea.

86
00:06:27,970 --> 00:06:33,790
Let's think back to the first problem, which is figuring out what the original rodding oranges were

87
00:06:33,790 --> 00:06:35,530
before we even start the rotting pattern.

88
00:06:36,460 --> 00:06:42,400
In order to make sure that we have all of the rotting oranges at the very beginning, what we have to

89
00:06:42,400 --> 00:06:48,460
do is we need to scan through the entire Tuti array and then figure out the positions of all of the

90
00:06:48,460 --> 00:06:52,510
rotting oranges so we know where to begin our rodding pattern.

91
00:06:53,080 --> 00:06:57,760
Once again, we have an implement the pattern yet, but we know that we need to make sure that we check

92
00:06:57,760 --> 00:07:05,290
the entire data structure to find all of the tubes because we're going to scan through the entire 2D

93
00:07:05,290 --> 00:07:05,560
array.

94
00:07:05,560 --> 00:07:10,810
Anyways, in the very beginning, we might as well group that with the fact that we're also counting

95
00:07:10,810 --> 00:07:12,250
all of the fresh oranges.

96
00:07:12,470 --> 00:07:15,160
It's pretty much the exact same sequential traversal.

97
00:07:15,400 --> 00:07:17,200
But now we just split up the logic.

98
00:07:17,530 --> 00:07:22,020
If we see it too, we make sure that we account for the fact that there's a rotting orange here.

99
00:07:22,060 --> 00:07:28,000
If we see a one, we just increase the count of the number of fresh oranges and then we can use that

100
00:07:28,000 --> 00:07:30,350
beginning solution to this problem.

101
00:07:30,970 --> 00:07:36,490
So here we've kind of tackled two different sub problems and we can identify the very least.

102
00:07:36,490 --> 00:07:41,410
That's sequential order is something that we want at the very beginning.

103
00:07:41,680 --> 00:07:43,610
We just want to solve the two problems first.

104
00:07:43,870 --> 00:07:47,020
The first is what are the initial rotting oranges?

105
00:07:47,320 --> 00:07:51,720
And the second is how do we keep track of fresh oranges?

106
00:07:52,180 --> 00:07:56,050
So here I'm just going to say keep track of fresh oranges.

107
00:07:56,890 --> 00:07:59,470
So these are the two problems we need to solve with sequential order.

108
00:08:00,550 --> 00:08:06,040
So here we've identified a starting point with our sequential order, this solves some of our problems,

109
00:08:06,040 --> 00:08:07,220
but not all of our problems.

110
00:08:07,480 --> 00:08:15,880
The main problem left to solve is figuring out how to implement the logic for this rodding order that

111
00:08:15,880 --> 00:08:16,630
we have to do.

112
00:08:17,640 --> 00:08:24,270
So here we know that we want to start rotting outwards in the immediate vicinity of our starting to

113
00:08:24,270 --> 00:08:32,160
oranges, we want to rot outwards into whatever fresh oranges are in the immediate up, right down and

114
00:08:32,160 --> 00:08:38,710
left of any of these rotting oranges and then do the same for the next level of rotting oranges.

115
00:08:39,270 --> 00:08:46,290
The problem is that the order in which we do it has to be tracked in a minute to minute basis.

116
00:08:46,680 --> 00:08:52,760
In some ways you want to see that every ring that we expand outwards from represents a new minute.

117
00:08:53,070 --> 00:09:00,180
And those rings are combined when you group the number of oranges that there are at every level.

118
00:09:01,060 --> 00:09:06,820
If we think about it, we kind of get the instinct that this level by level traversal order is going

119
00:09:06,820 --> 00:09:11,350
to be breadth first search, because as we know with breadth of research, that's exactly the definition.

120
00:09:11,650 --> 00:09:17,860
It picks a starting point and then it starts expanding outwards into the immediate neighbors in these

121
00:09:17,860 --> 00:09:18,720
four directions.

122
00:09:18,760 --> 00:09:21,570
So we know breath research is definitely the right traversal order.

123
00:09:21,970 --> 00:09:29,440
The problem is figuring out how we group it into these minutes appropriately, because when we think

124
00:09:29,440 --> 00:09:37,270
about our breath for a search implementation, we know that we're implementing a Q and a Q. processes

125
00:09:37,450 --> 00:09:39,130
elements one at a time.

126
00:09:39,220 --> 00:09:45,040
It doesn't know whether or not this elements and this elements are at the same level.

127
00:09:45,040 --> 00:09:48,010
So it doesn't know how to implement that break.

128
00:09:48,310 --> 00:09:50,650
And that's where we need to implement it.

129
00:09:50,860 --> 00:09:52,330
This is where we need to get creative.

130
00:09:52,930 --> 00:09:58,050
And this is actually where I want to challenge you to try and think about what to do.

131
00:09:58,690 --> 00:10:04,660
You already know that at the very beginning you have access to the two rodding oranges because we've

132
00:10:04,660 --> 00:10:06,300
already done the sequential order PA.

133
00:10:06,490 --> 00:10:08,430
We've scanned through the entire 2D array.

134
00:10:08,470 --> 00:10:11,350
We know where the two rodding oranges are from here.

135
00:10:11,350 --> 00:10:16,630
We want to start implementing breath for search from the two rodding oranges, but we want to make sure

136
00:10:16,630 --> 00:10:22,810
that we're able to properly track the amount of minutes that are passing whenever a level of orange

137
00:10:22,810 --> 00:10:25,000
is decays and rots away.

138
00:10:25,940 --> 00:10:31,700
So try and figure out a creative solution here, and there's actually multiple ways that you can do

139
00:10:31,700 --> 00:10:34,010
this, we've even done a way already.

140
00:10:34,010 --> 00:10:38,990
If you think back to a binary tree question we did with Breadth First search, there was a point where

141
00:10:38,990 --> 00:10:41,630
we needed to get the level order of a tree.

142
00:10:41,630 --> 00:10:47,960
And the only way we could do so is if we implemented some kind of tracking system that told us when

143
00:10:47,960 --> 00:10:50,630
we were at the start or the end of a level.

144
00:10:50,960 --> 00:10:55,580
I don't know if you remember this question, but if you think back to the solution there, it's very

145
00:10:55,580 --> 00:10:57,320
similar to what we can do here.

146
00:10:57,710 --> 00:11:03,080
Either way, come up with a solution yourself and we can do this together in the next video.