Rotten oranges problem | Leetcode

This video explains a very frequently asked programming interview question which is to find the time taken to rot all oranges in a basket of orange. This video explains the most efficient way to solve this problem with example. Time complexity of the algorithm is O(N) which is the best time for this problem. CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...

[@supernova7870]

Sir, at the starting of the program we are required to put all the rotten oranges in the queue and for that we have to look entire 2d array to get those oranges , so time complexity is O(N^2) at the starting only and you said it will be O(N). PlZz clear it??

[@techdose4u]

I wrote O(N) thinking N = No of cells. No of cells = Row*Cols. So basically TIME is O(N*M). Sometimes I miss to say certain details.😅

[@supernova7870]

@@techdose4u okk sir, i got it :)

[@tarunkumar.d8379]

@@techdose4u Respect ✨

[@ashfaaqmir7869]

@@techdose4u You should apologize publically for such mistakes

[@pythontek]

🤣

[@viralindian8326]

By watching your two videos of rotten oranges and number of islands...I am feeling comfortable with Graph theory of BFS and DFS now... Thanks dude 😋

[@techdose4u]

Welcome :)

[@shashikantkumar5095]

Thank you, Sir, for providing premium level videos free of cost to us, After getting placed I would like to donate and support this channel.

[@techdose4u]

Thanks for supporting :)

[@rohithreddy5201]

Have you been placed yet? :)

[@divyagupta6854]

Sir, you explained the algorithm so well, and I was able to code it properly too!! Just two edge cases need to be considered while coding this algorithm, that when we have rotten orange at edge of the grid anywhere, we might check a fresh orange in out of bounds of grid, so we have to also check that coordinate's x - 1, or coordinate's y - 1, or coordinate's x + 1, or coordinate's y + 1 must be in index range of grid. And we also have to keep a global variable to regularly update it whenever timestamp is being increased, so that, even though our queue gets empty and we won't have access of its last element, we have the last updated value of timestamp globally.

[@souravbarik8470]

Reaction when you read the probelm statement: "its so god damn hard" After explanation: "So damn easy"

[@techdose4u]

😂

[@sushantpatial9819]

Alternatively, we can keep count of all the fresh oranges while adding the indices of rotten oranges to the queue. While checking for all the indices in the queue, we will decrease the fresh oranges count if we encounter a 1. In the end if our fresh oranges count is greater than 0, that means we still have fresh oranges left in the basked and we can return -1 :)

[@surbhitamrakar1638]

This is the best explanation for this problem..such a great channel.

[@techdose4u]

Thanks :)

[@TechBrain811]

Love your explanation, please keep up tha good work. You are the hero we don't deserve, But you are the hero we need. ...

[@techdose4u]

😅 Thanks bro

[@niharikagrover3523]

Could you explain where we should use BFS and in which scenarios we can used DFS, I know that will come from practice but still a video explaining this concept will be helpful

[@ivanleon6164]

an easier way to check if all oranges are being rotten(IMO) is at the initial scan just count how many oranges are there(1 or 2), then when adding an element to the queue you can count how many you have added, if those 2 counters are the same, then all oranges were rotten at the end.

[@abhishekgautam1063]

Number of rows are N and let M be the number of columns. Also we'll be traversing the whole grid so will the complexity be O(N*M) ??

[@techdose4u]

By N i meant no of cells 😅 so N is actually NM because we need to travel all cells. Dint clearly mention that part.

[@debaratighatak2211]

The best and the most intuitive explanation ever, thank you so much!

[@techdose4u]

Welcome :)

[@rahulkumarbarik7584]

quality content free cost , god do exist. Hence prove

[@techdose4u]

Thanks

[@rohannegi1330]

This explaination makes a complex problem very easy to understand. Nice work @TECH DOSE. Keep doing the good work.

[@jordanwoltjer2024]

Great explanation. Would also be nice to see the concept implemented in code after the explanation.

[@jaswantrohila3776]

Too good... Your channel's video are always on my top priority.... thanks god your are here to help....and also thanks to you....💥

[@techdose4u]

😅Welcome

[@ANKURSingh-yl2lj]

really a great explanation and also voice is very clear

[@techdose4u]

Thanks

[@ash_engineering]

Sir please post more such leetcode problems .. they are very usefull

[@techdose4u]

Many have requested for the same and so I decided to include leetcode problems as well. In future you will see many more.

[@arunmozhichelvanscse7349]

an Awesome explanation😊😊

[@techdose4u]

Thanks 😊

[@ayanraj6295]

Thanks for such a nice explanation. Here's my easy implementation: class Solution { public: int orangesRotting(vector& grid) { vectortime(grid.size(),vector(grid[0].size(),0)); vectorvisited(grid.size(),vector(grid[0].size(),0)); int ans=0; queueq; for(int i=0;i

[@pusarlaaishwarya5035]

You are helping students like us...tqs a lot... ❤️❤️❤️❤️

[@techdose4u]

Welcome :)

[@ashishverma1382]

great explanation

[@techdose4u]

Thanks 😊

[@mma-dost]

is this the optimized code. Its somewhat looks like bruteforce. We are using space for storing all those nodes.

[@rajivsarkar277]

@Tech Dose why this problem is not possible to solve with DFS. because it seems to be similar to search island problem.

[@tianagreisel3923]

Your explanations are so good! Thank you for all of your videos. Very, very helpful!!

[@techdose4u]

Welcome 😊

[@srutiverma6977]

class Solution { public: //Function to find minimum time required to rot all oranges. struct Node{ int t; int r,c; }; int orangesRotting(vector& grid) { // Code here queueq; Node* node; int n=grid.size(),m=grid[0].size(),count; for(int i=0;ir=i; node->c=j; q.push(node);} while(!q.empty()){ Node* a=q.front(); q.pop(); // coutr,j=a->c,ti=a->t; count=ti; if(0r=i+1; node->c=j; q.push(node);} if(0r=i; node->c=j+1; q.push(node);} if(0r=i-1; node->c=j; q.push(node);} if(0r=i; node->c=j-1; q.push(node);} } for(int i=0;i

[@techdose4u]

👍🏼

[@yashpreetbathla4653]

thank you sir v imp problem ❤️

[@techdose4u]

Yea its very frequently asked :)

[@deepjyotsinghkapoor1955]

what a explanation! wow!

[@techdose4u]

Thanks :)

[@i_DeepakV]

Awesome video, thanks for explaining it, in simple way.

[@tushar6286]

Sharp & clear explanation!! Keep it up sir!

[@techdose4u]

Thanks :)

[@dikshamalik2565]

So nice explanation

[@cutiex7357]

Your explanation was so good and I understood perfectly. Thank You!!

[@konakandlarohith6681]

Sir,Can you please explain the implementation of the code also from next time???

[@techdose4u]

Sure

[@sagarksahoo4667]

Shouldn't the time complexity be O(m*n) ??

[@manasvinsharma1740]

This is God level explanation 🤩

[@techdose4u]

😀

[@ksquare1112]

Best and clear explanation. Thanks

[@techdose4u]

Welcome :)

[@aakashgoswami2356]

Sir i have 2 doubt : 1.Sir in your code ,in line 61 ,what is the purpose of writing temp.x = -1 ,temp.y = -1 and i dont't understand delimeter part. 2. My second doubt is when i submit code on leetcode ,it is showing heap buffer overflow on address... plzz solve above 2 problems asap.

[@reetverma6876]

Sir ,why we use delimeter ?? As in ur code u r using delimiter ..

[@techdose4u]

Forgot the code compeltely 😅

[@keshavtawari2979]

thanks a lot, clear and precise explanation

[@techdose4u]

Thanks

[@ANKURSingh-yl2lj]

sir please also provide link for most optimized code i will able to write the code but thats nt most optimised

[@techdose4u]

I am putting optimized codes from last 4 months. I will add from now on.

[@hrushikeshpatil3772]

Inspired from Corona......

[@spetsnaz_2]

xD

[@nknidhi321]

Awesome 🙏

[@techdose4u]

Thanks

[@v.sreesairam9488]

understood bhaiya thank your very much :)

[@techdose4u]

Welcome

[@prateeksinghal630]

Nice Explaination!!

[@techdose4u]

Thanks :)

[@prachurjyabasistha4682]

very nice explanation!

[@techdose4u]

Thanks :)

[@pragyasingh9543]

Sir can you provide the implementation code for this problem

[@techdose4u]

Is it not present in link ?

[@pragyasingh9543]

Got it sir thanku

[@NinjaCoders]

bhai code kaha hai ?

[@spetsnaz_2]

Awesome explanation! This is a simple implementation of the above explanation:::::: int orangesRotting(vector& grid) { if(grid.empty()) { return 0; } int counter{0}; queue q; for(auto row=0; row

[@Shuvooa]

brilliant

[@techdose4u]

Thanks :)

[@lakshayv3272]

[@techdose4u]

Thanks :)

[@revarevanth1800]

Thank you sir!!!

[@techdose4u]

Welcome :)

[@adarshsharadpandey4763]

Drop servicing == Dalaali returns true!!!

[@prashantverma3347]

Thank you

[@techdose4u]

Welcome

[@niveditha-7555]

Such an easy explanation, you have become my favorite youtuber

[@techdose4u]

Thanks :)

[@dexkode5558]

Subscribed!! I'm glad I find this channel

[@techdose4u]

:)

[@bathininipun9797]

Add the code too!

[@techdose4u]

👍

[@sandeeprajurs1994]

is space complexity O(1), because at the end we don't have any elements in the queue?

[@techdose4u]

No, because we are using queue.

[@sohinidey6711]

Can I use dfs? I traverse every element in the matrix and use dfs for every element if the element is 2.. time complexity will be O(m*n) . Will that process be right?? we don't need to check for element value 1 if top, down,left,right any element is 2 or not...we will keep one variable which will store Maximum time frame..

[@techdose4u]

I don't think DFS will work because you need to process all cells with same timeframe simultaneously. Try submitting using BFS.

[@sohinidey6711]

@@techdose4u ok.. how I ll understand which method(dfs/bfs) we have to use? This concept is not clear.

[@eduardozevallos1509]

Tech Dose you are amazing. I can't watch anyone elses leetcode explanations

[@techdose4u]

❤️

[@hardiknahata4328]

Explanation was good, but I lack skills when transforming ideas to code. Hope you will cover that in future videos. Most of the programming tutorials lack that. Just my views. Thanks a lot

[@techdose4u]

What exactly?

[@hardiknahata4328]

Explanation of the code and a trace probably

[@prakharagarwal6237]

We can also do level order traversal where we keep track of the current level so that we wont have to maintain nodes.

[@techdose4u]

👍🏼

[@nitin5865]

Thanks a ton sir 👍

[@techdose4u]

Welcome :)

[@E__ShameemAhamedS]

you made the problem as easy as addition of two problems

[@techdose4u]

Thanks 😅

[@E__ShameemAhamedS]

@@techdose4u i will definitely donate and support our channel after i got placed

[@AhmadRazaUnique]

Sir, there may be -1 is the answer when we have some neighbor 1 to 1. Its not for sure that the answer will be other than -1 when we dont have any 1 sorrounded by 1 or 2.. Please clearify sir

[@peeyooshmanitiwari9082]

thank you sir..

[@techdose4u]

Welcome

[@sukritkapil2562]

to the point explanation. thanks a lot!

[@techdose4u]

Welcome :)

[@hapysethi1306]

Sir claps for you

[@techdose4u]

Thanks

[@2018-o2p]

Best Explanation till date!

[@techdose4u]

Thanks :)

[@mohithkailash]

Someone get this man an award

[@vaibhavchawla2439]

Quality content 😍😍😍.

[@Od253]

👍🏾