Rotting Oranges - Leetcode 994 - Python

🚀 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.

[@NeetCode]

More Graph Problems: kzbin.info/www/bejne/q6WnpmaHbKufqNk

[@RichardLopez-lr4el]

If I pass any coding interview, it is because of this channel!!! Keep up the amazing work! 👏🏽

[@varunshrivastava2706]

Have you passed any? (Please say yes 🤞)

[@RichardLopez-lr4el]

@@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!

[@bucketsort3248]

​@@RichardLopez-lr4el Wow congrats on being Noogler! How long do you study to prepare for your interview?

[@terellkantwell6876]

@@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.

[@nithinsastrytellapuri291]

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

[@americanonobrasil2128]

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!

[@TheSahilpadyal]

NeetCode is a lifesaver. The way you explain the problem and the code is just amazing. Keep up the good work

[@ammarqureshi2155]

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

[@nickng8069]

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

[@ax5344]

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!

[@prashanthkurella4500]

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.

[@gustavo-yv1gk]

hey do u have that code for dfs?

[@huseyinbarin1653]

very clean solution liked it. Thanks

[@rajaroy43]

This question was asked in an Amazon interview (SDE2)

[@matthewzhang7330]

I literally finished this question two days before you post this! lol. Glad that my solution is very similar to yours.

[@BharathKalyanBhamidipati]

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?

[@vour6654]

@@BharathKalyanBhamidipati Structy

[@ritikajaiswal3824]

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.

[@varunshrivastava2706]

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.

[@georgebian5383]

so beautiful. Thank you!

[@jaimodha7523]

Amazingly explained :)

[@krateskim4169]

as always ,a beautiful solution

[@mingjuhe1514]

Thanks man. Very great Video!

[@grovestreet9165]

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

[@YasirYSR]

awesome. keep going.

[@nikhilchauhan5837]

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.

[@nihao852]

You are my hero! Thank you

[@yadavankit]

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 KZbin decided on it's own that its time for me to learn it 😛

[@adityatulsiyan1158]

good for you brother.

[@sanskarkumar7285]

Amazing explanation sir. Greetings from India

[@shouryannikam3949]

Thank you for your service. I've recommended your channel to every CS major that I know.

[@NeetCode]

Thanks, much appreciated!

[@SidddB]

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.

[@mirrorinfinite5392]

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.

[@shubhammishra1225]

Wow nice solution.. We can use tuples instead array to save more space.

[@gabchen3000]

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!

[@DorKati]

thanks man!

[@asdfgmnbvczxcv]

Alternatively you can use dfs but only update a cell if it took less time to get there from a previous source

[@asdfasyakitori8514]

Great video

[@markolainovic]

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

[@EranM]

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..

[@mr6462]

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?

[@bchen1403]

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?

[@hamoodhabibi7026]

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

[@fatiharslan7849]

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

[@yuenyiupang]

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?

[@hamoodhabibi7026]

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

[@dmytro.pyvovarenko]

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.

[@qm495]

thank you

[@azharuddin6096]

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?

[@mermaid6380]

I remember seeing this problem at your channel before. At that time it was fresh set and rotten queue.Do I get incorrect memory?

[@JJ-qv8co]

commie stay in CN.

[@georgebian5383]

Thanks!

[@NeetCode]

Thank you so much 🙏

[@arashkoushkebaghi1432]

So, what do we do if this video wasn't help? Should we just chuck our laptops at the wall?

[@mathesharutchezhian6525]

Can you please do qn no.721 Merge Accounts ?

[@Dun1007]

what is time complexity?

[@soanonso]

You forgot to use your ROWS and COLS vars when doing a bounds check.

[@yasirmalik198]

popleft is not for popping more recently added oranges

[@danielsun716]

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

[@lucasnbsb1]

I'm down for pretty much any orange-based problem

[@titniumultd]

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

[@nikhil_a01]

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.

[@MetinOrak]

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.

[@kirillzlobin7135]

Maaaaaaaaaaaaaaaaaaan, you are the legend

[@jaeen7665]

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.

[@tucker1351]

🐐

[@harishsn4866]

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.

[@Redbugist]

why in line 24 is 'continue' but not 'return'?

[@hamoodhabibi7026]

because this is BFS not DFS we aren't using recursion so there is no call stack to return :p

[@sergiofranklin8809]

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

[@nikhil_a01]

Both passed for me. Are you sure you don't have some other problem in the code?

[@grovestreet9165]

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

[@andreytamelo1183]

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; } }

[@andreytamelo1183]

leetcode/problems/rotting-oranges/discuss/2107622/C-straightforward-brute-force-O(n*m)-fresh-first-easy-to-understand

[@nichtverstehen2045]

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.

[@lakhbawa]

why cannot you use simple python, :< i am PHP / Java / JavaScript programmer, i am having to learn advance python to understand it :(

[@ammarqureshi2155]

what part of it is advanced python? his code is as simple as it gets, its basically pseudocode at this point

[@abhicasm9237]

😆

[@jaslinkaur645]

I think he's referring to the data structure like queue and deque

[@donaldcodes]

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