Rotting Oranges - Leetcode 994 - Python
Vložit
- čas přidán 5. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: neetcode.io/problems/rotting-...
0:00 - Read the problem
2:05 - Drawing Explanation
6:05 - Coding Explanation
leetcode 994
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
More Graph Problems: czcams.com/video/utDu3Q7Flrw/video.html
If I pass any coding interview, it is because of this channel!!! Keep up the amazing work! 👏🏽
Have you passed any? (Please say yes 🤞)
@@varunshrivastava2706 haha yes 🎉! I just heard back yesterday, and it looks like I’m going to be coworkers with Neetcode!! I’m in a different office, but I can’t say enough good things about how much this channel has helped!
@@RichardLopez-lr4el Wow congrats on being Noogler! How long do you study to prepare for your interview?
@@RichardLopez-lr4el hey man i am currently in the process of finding a job, any tips of how you studied to get good at general problems? I struggle a lot starting problems but im starting to see a pattern where some problems are very similar to others in the sense that the solution is the same and differs but a couple lines of code.
I could figure out that this is a BFS problem and started coding it. But the multi BFS approach was out of my reach. Thanks for another great video
NeetCode is a lifesaver. The way you explain the problem and the code is just amazing. Keep up the good work
Great as always. Thanks, man. It's funny, when I first started watching I'd ususally skip to the end for the answer and not understand very well if I encountered the problem again or a similar one. The more I watch, the more I realize how important it is to comprehend all the concepts you're talking about and now I watch patiently and try to absorb everything. No excuses for why I wasn't doing that earlier. Thanks again!
This question was asked in an Amazon interview (SDE2)
great explanation, this problem would have similarities with the Walls and Gates leetcode problem that you have done previously. keep up the good work :) we appreciate it
Thanks so much for explaining why we cannot use while loop but have to use a list at 9:27!
I saw their code but I just did not get it! You really know where we got stuck!
Thank you for some explanations here that I was looking for when looking at results on leetcode such as the for loop used to take snapshot, and it run in one unit time
You can do this with DFS as well. DFS will visit every orange that BFS does but in the wrong order if you can keep track of what the time was when you visit a certain orange you can just increment that time when you visit the node. All this boils down to is basically finding out the maximum "depth" of the graphs. If there are multiple partitions, you return the maximum time it takes a partition to rot.
hey do u have that code for dfs?
I literally finished this question two days before you post this! lol. Glad that my solution is very similar to yours.
Hey! I've covered almost all the data structures upto trees but graphs. Finding graphs a little difficult to even get started with. Could you please share any good resources where I can learn graphs from?
@@BharathKalyanBhamidipati Structy
There are many channels for leetcode solutions for python, but the way you explain is just mind blowing... Ever since I have started only your channel is helping me.. However, When I can't find solutions on your channel for various questions I don't even understand it at the end because nobody is explanation is sufficient. Hence, I'm requesting you to do more leetcode questions I know youre a noogler now, you have been busy but PLEASE I'm requesting you to continue making leetcode solutions.
Agree with you Ritika the major problem with people who study DSA with Python is lack of good resources. Although you can join the discord server of Official Python community and post your doubts there. I do the same and its really helpful.
the explanation is soo good that you don't even need to watch half of the video the way you think and explain is soo good
very clean solution liked it. Thanks
Great and easy to understand video. Suggestion: can you make video on sliding windows problem.. like find minimum number of operations to make that fixed size window satisfy some condition.
Thank you for your service. I've recommended your channel to every CS major that I know.
Thanks, much appreciated!
Over the course of 8-9 years, this question is asked to me thrice in different forms and somehow I wasn't completely able to solve it. I even tried searching a solution online but no luck probably due to different terminologies (zombies / virus / even rotten eggs). Today CZcams decided on it's own that its time for me to learn it 😛
good for you brother.
Thanks for another great video! I was wondering if you could maybe give an expanded explanation for the "snapshot" for loop inside the while loop? Having a bit of trouble understanding its purpose since we have the main while loop already iterating.
We need to use the for loop with len(q) because len(q) is only evaluated once at the start of the current time loop. So for each rotten orange at that certain time, we pop it and add the new rotten oranges to the queue. If we use something like while(q) instead of the for loop with len(q), it will keep going because we append new rotten oranges to the queue, making it hard for us to keep track of the time.
as always ,a beautiful solution
so beautiful. Thank you!
Wow nice solution.. We can use tuples instead array to save more space.
Amazing explanation sir. Greetings from India
Thanks man. Very great Video!
I found it less confusing if I popleft one at a time instead of 3 at a time in this example by passing in a time variable into the queue with the r,c and make sure to increment time when a good orange turns rotten. The directions array + loop makes it hard for me to follow along while I run through an example. Here is my approach, hope this helps people with my kind of monkey brain:
ROWS = len(grid)
COLS = len(grid[0])
maxTime, goodOrange = 0, 0
q = collections.deque()
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
q.append((r,c,0))
if grid[r][c] == 1:
goodOrange += 1
while q:
r, c, time = q.popleft()
maxTime = max(maxTime, time)
if r+1 < ROWS and grid[r+1][c] == 1:
goodOrange -= 1
grid[r+1][c] = 2
q.append((r+1,c,time+1))
if r-1 >= 0 and grid[r-1][c] == 1:
goodOrange -= 1
grid[r-1][c] = 2
q.append((r-1,c,time+1))
if c-1 >= 0 and grid[r][c-1] == 1:
goodOrange -= 1
grid[r][c-1] = 2
q.append((r,c-1,time+1))
if c+1 < COLS and grid[r][c+1] == 1:
goodOrange -= 1
grid[r][c+1] = 2
q.append((r,c+1,time+1))
if goodOrange > 0:
return -1
return maxTime
As always great video, thank you for the explanation!
Amazingly explained :)
Alternatively you can use dfs but only update a cell if it took less time to get there from a previous source
You are my hero! Thank you
if we using popleft, is it not necessary to not have for i in range(len(q)), as it is already bfs, i mean i could just given a count together with x,y into q? is it? or that way is more clear?
it's neccessary for his code because he needs to go through the entire queue (thus simulating the spread of rotten simultaneously) to increment the timer count after all that. If we didn't have the forloop the timer would act like a dfs incrementing time one rotten path at a time
Thanks for this succinct explanation! I have a question, for line 15, is it really necessary to use "fresh > 0" as one of the loop conditions?
I am thinking of the same thing and I see no reason why it would yield error if I take out fresh > 0 condition but it actually did on example 1 provided on Leetcode. Have you figured it out?
It's needed because after we make our last fresh orange => rotten we append that last rotten orange to our queue and decrement fresh count by 1 (So we have 1 rotten in queue and 0 fresh). Now this theoretically shouldn't be a problem because in our code the line right after it "for i in range(len(q)" wouldn't run HOWEVER it is a problem because after it doesn't run the time variable will still be incremented resulting in us returning 1 minute extra where we do nothing in that extra minute
awesome. keep going.
I did it a bit differently, and it has a bit worse time complexity, but it was more intuitive for me this way. Basicaly, I'd go and mark all the oranges that are about to rot and I'd count that as a single increment in final counter. Then I'd go ahead and rot them. Repeat the process as long as the marking step returns True, i.e. at least one orange was found that is about to rot.
Code:
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
def directions(row, col):
return [
(row - 1, col),
(row, col + 1),
(row + 1, col),
(row, col - 1),
]
def valid(row, col):
return row in range(m) and col in range(n)
def has_fresh_oranges():
for row in range(m):
for col in range(n):
if grid[row][col] == 1:
return True
return False
def mark_oranges_about_to_rot():
rotten = False
for row in range(m):
for col in range(n):
if grid[row][col] == 1:
for r, c in directions(row, col):
if valid(r, c) and grid[r][c] == 2:
grid[row][col] = 3
rotten = True
return rotten
def rot_oranges():
for row in range(m):
for col in range(n):
if grid[row][col] == 3:
grid[row][col] = 2
res = 0
while mark_oranges_about_to_rot():
res += 1
rot_oranges()
return res if not has_fresh_oranges() else -1
you can also think of getting a "node" which is a root, and point at all rotten oranges in the begining. And then simple BFS solve..
dfs works for this algorithm. You can use a minute variable to check if the value is not empty or rotten and if it's bigger than current minute we can make it smaller.
class Solution {
public int orangesRotting(int[][] grid) {
for(int i=0;i
I think Leetcode may have added a new testcase that causes your solution to fail...
grid =
[[1],[2],[1],[2]].
In this case a q.popleft() is necessary, as otherwise our time increments an additional step
Solution still looks fine to me. The code on NeetCode's github passes. I'm doing it the same way as NeetCode and it passes.
The fresh > 0 check prevents time from incrementing an additional step.
I kinda had a similar issue, but solution is correct. I didn't assign the length of queue to a new variable and it was increasing while adding new items to queue. After assigning it to a new variable and using in the loop condition, it worked well.
thanks man!
Just got done with this problem, I solved it even though I never came across multi-bfs pattern before. I was thinking about this problem in a little bit different way. However it was not working if there were more than 1 rotten oranges in the beginning. All I was missing was to put all the rotten oranges in the queue in the start and it worked after that. But this idea came to me from reading some comment. I don't know if should I mark this problem as solved by me?
I remember seeing this problem at your channel before. At that time it was fresh set and rotten queue.Do I get incorrect memory?
commie stay in CN.
I doubt that you can do it with DFS anyhow. The DFS implies making a sequenced search in-depth till the very end. BFS makes queues to stack search tasks and computing minutes is much easier. Thus, BFS is the only option here.
I tried to solve this problem with DFS, but while doing that, I find it more and more wrongly. Then I realize I have to do it by multi-source BFS.LOL
Great video
So, what do we do if this video wasn't help? Should we just chuck our laptops at the wall?
I'm a month and a half into my LeetCode grind. I can't believe a company would say: "Yeah, I need you to do LC 994, no aide, of the top of the dome." Really? smdh.
Can you please do qn no.721 Merge Accounts ?
Amazing video
what is time complexity?
thank you
You forgot to use your ROWS and COLS vars when doing a bounds check.
🐐
popleft is not for popping more recently added oranges
I'm down for pretty much any orange-based problem
Maaaaaaaaaaaaaaaaaaan, you are the legend
Thanks!
Thank you so much 🙏
why in line 24 is 'continue' but not 'return'?
because this is BFS not DFS we aren't using recursion so there is no call stack to return :p
I came up with this solution but didn't occur to me that I should add fresh > 0 condition and wasted a lot of time.
I don't know why but, if you use: directions = [[0, 1],[1,0],[-1,0],[0,-1]] it will fail, but if you use: directions = [[0, 1],[0,-1],[1,0],[-1,0]] it will pass. Please can anyone explain why, both of them are doing the same thing
Both passed for me. Are you sure you don't have some other problem in the code?
c++ Solution:-
class Solution {
public:
struct triplet{
int i; // ith index
int j; // jth index
int time; // time
};
int orangesRotting(vector& grid) {
queue q;
const int x[4]={-1,0,1,0};
const int y[4]={0,-1,0,1};
int fresh_oranges=0;
int oranges_rottened=0;
for(int i=0;i
Fresh-first (vs demonstrated rotten-first) approach (C#):
public class Solution {
public int OrangesRotting(int[][] grid) {
int rows = grid.Length;
int columns = grid[0].Length;
HashSet freshes = new();
for (int row = 0; row < rows; row++)
for (int column = 0; column < columns; column++)
if (grid[row][column] == 1) freshes.Add((row, column));
int generations = 0;
do
{
List toSpoil = new();
foreach (var fresh in freshes)
{
bool badAbove = fresh.row > 0 && grid[fresh.row - 1][fresh.column] == 2;
bool badOnRight = fresh.column + 1 < columns && grid[fresh.row][fresh.column + 1] == 2;
bool badBelow = fresh.row + 1 < rows && grid[fresh.row + 1][fresh.column] == 2;
bool badOnLeft = fresh.column > 0 && grid[fresh.row][fresh.column - 1] == 2;
if (badAbove || badOnRight || badBelow || badOnLeft) toSpoil.Add(fresh);
}
if (toSpoil.Count == 0) break;
foreach (var spoiled in toSpoil)
{
freshes.Remove(spoiled);
grid[spoiled.row][spoiled.column] = 2;
}
generations++;
} while (true);
return freshes.Count == 0 ? generations : -1;
}
}
leetcode/problems/rotting-oranges/discuss/2107622/C-straightforward-brute-force-O(n*m)-fresh-first-easy-to-understand
that kind of testing is only meaningful if you have nothing else to assess on a candidate like fresh graduate with zero experience. otherwise it's a good chance to miss opportunity to hire someone skillful and knowledgeable but not that good at "challenges" that are not even close to real software developer job challenges.
next time use tuples instead of lists. in many if not most scenarios set is better than deque and lists are unhashable.
learn `elif` - that could be life saver in real life.
and please stop creating classes at will. It's Python not Java.
why cannot you use simple python, :< i am PHP / Java / JavaScript programmer, i am having to learn advance python to understand it :(
what part of it is advanced python? his code is as simple as it gets, its basically pseudocode at this point
😆
I think he's referring to the data structure like queue and deque
I'm dumb when it comes to understanding algos and I get his solution. I recommend brushing up on BFS if you don't understand this solution, because graphs are based on traversal algorithms like BFS and DFS