Rotting Oranges - Leetcode 994 - Python

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

[@TheSahilpadyal]

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

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

[@rajaroy43]

This question was asked in an Amazon interview (SDE2)

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

[@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?

[@MdRahman-lf9iv]

@@gustavo-yv1gk here you go (this already beats 100% so i didn't optimize it, but technically you could optimize it using another n*m matrix): class Solution { final int INF = Integer.MAX_VALUE; public int orangesRotting(int[][] grid) { //well need to find the minimum time in each cell //rather than searching from the rotten fruits //we can dfs from our fresh fruits and find the closest rotten fruit //if there is a freshfuit that has 0 connections to rotten fruits //we return -1; //the fruit that is the furthest from a rotten fruit int max = 0; boolean[][] visited = new boolean[grid.length][grid[0].length]; for(int r = 0; r < grid.length; r++){ for(int c = 0; c < grid[0].length; c++){ //we found a fruit we need to find it's nearest if(grid[r][c] == 1){ int val = dfs(visited, grid, r, c, 0); if(val == INF){ return -1; } //if this is the furthest cell from a rotten fruit then update it max = Math.max(max, val); } } } return max; } //distance = distance from nearest rotten fruit. Each distance = 1 min private int dfs(boolean[][] visited, int[][] grid, int r, int c, int distance){ //we have reached the edge but didn't find a rotten fruit if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length){ return INF; } if(visited[r][c] || grid[r][c] == 0){ return INF; } if(grid[r][c] == 2){ return distance; } visited[r][c] = true; int leftRight = Math.min(dfs(visited, grid, r+1, c, distance + 1), dfs(visited, grid, r-1, c,distance + 1)); int downUp = Math.min(dfs(visited, grid, r, c+1, distance + 1), dfs(visited, grid, r, c-1,distance + 1)); visited[r][c] = false; return Math.min(leftRight, downUp); } }

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

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

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

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

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

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

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

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

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

[@KNRG04]

@@mirrorinfinite5392 2 years later and you've saved me, thank you

[@asdfgmnbvczxcv]

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

[@arashkoushkebaghi1432]

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

[@prathamhebbar5800]

Could you maybe explain why we are popping from the left?

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

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

[@ashwanikumar415]

@NeetCode why visited was not used , since if there are multiple rotten oranges this solution will run on those nodes again , right ?

[@kaushik.aryan04]

no as we are marking oragnes with 2 whenver we add them to queue and if an orange is 2 we continue from the loop so vistited is not required

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

[@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?

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

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

[@huseyinbarin1653]

very clean solution liked it. Thanks

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

[@shubhammishra1225]

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

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

[@sanskarkumar028]

Amazing explanation sir. Greetings from India

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

[@soanonso]

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

[@DBagg-zz4ip]

I made the same pop instead of popleft mistake. That cost too much time to figure out.

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

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

[@georgebian5383]

so beautiful. Thank you!

[@mathesharutchezhian6525]

Can you please do qn no.721 Merge Accounts ?

[@kirillzlobin7135]

Amazing video

[@krateskim4169]

as always ,a beautiful solution

[@mingjuhe1514]

Thanks man. Very great Video!

[@nihao852]

You are my hero! Thank you

[@lucasnbsb1]

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

[@yasirmalik198]

popleft is not for popping more recently added oranges

[@YasirYSR]

awesome. keep going.

[@prathamhebbar5800]

Can you explain why we are popping left?

[@TheBoon24]

We pop left because queues follow a first in last out policy. In terms of BFS this is helpful because we are appending elements to the end of our queue which is the same thing as adding elements to the RIGHT of queue. Since the most recent elements in our queue are on the right side, that means our least recent elements are on the left. In a queue we want to pop the least recently added elements

[@georgebian5383]

Thanks!

[@NeetCode]

Thank you so much 🙏

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

[@jaimodha7523]

Amazingly explained :)

[@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?

[@asdfasyakitori8514]

Great video

[@qm495]

thank you

[@DorKati]

thanks man!

[@Dun1007]

what is time complexity?

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

[@kirillzlobin7135]

Maaaaaaaaaaaaaaaaaaan, you are the legend

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

[@tucker1351]

🐐

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

[@BananaButcher]

Orange

[@BananaButcher]

Oinge

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