G-10. Rotten Oranges | C++ | Java

GfG-Problem Link: bit.ly/3oekoir
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79

[@animecontent2056]

Don't have an account in Instagram and it distracts me much more than anyone does 😎😎😎

[@aditidey5227]

Understood

[@herculean6748]

I am yet to start Tree and Graph, should start graph first? or do I need to do tree first?

[@getgoin2217]

really appreciate you putting quality content , but did not understand from explanation so clarifying here my understanding the TC is O(n*m) because of adding starting points in the queue + O(n*m*4) is because of BSF also worst case is not all oranges being fresh but 1 orange being rotten with rest all being fresh

[@Codebond7]

where is java code I am unable to find

[@sidduroy9150]

I can complete the whole playlist in one day , coz it's just like a Webseries 😂😊, Offcourse it's only bcoz of the Lead character: striver

[@manishprajapati8544]

😂😂😂

[@vishakhas1867]

Agreed bro

[@monumishra9638]

Agree

[@sidduroy9150]

@@monumishra9638 hey guys , how far your preparation came

[@sidduroy9150]

@@vishakhas1867 how far

[@av21015]

I really appreciate your dedication. This video is already recorded in stacks and queues playlist but you have recorded it again here. And this video is better than previous one.

[@takeUforward]

Yes, true, I agree

[@patrickishere]

​@@takeUforward which tool do you use to explain? it is so good !

[@SatyaMantha]

Striver, I like the way you make toughest problems look so easy with your explanation. Kudos to you!

[@vaibhavagarwal2421]

instead of using pair we can use vis grid to store the time as well

[@suheabkhan2546]

understood bahut chota compliment hai.... Dil khush hojata hai aap say padke bhai

[@RohitKumar-dz8dh]

For sure no one need to worry about code in any language after getting approach how to tackle problem 😊. Thanks again .

[@nipu8406]

Thanku sir for interview centric problem solving on graph because most of the UTube channels have algorithm of graph with no problem solving based on the concepts .

[@johnj171]

really great but what is exceptional is the connection you create between every problem and the volume of problems solved it builds up a strong foundation for every one slowly and strongly highly recommended for every one!!!!!!!!

[@rishabhsingh3873]

for delRow and delCol we can use array directions = {-1, 0, 1, 0, -1} and inside for loop for neighbor row and column we can use int nRow = r + directions[i]; int nCol = c + directions[i+1];

[@shiblijamal8544]

Anything is fine make sure the coordinates traverse all those direction that's it... Btw good thinking

[@LowkeyCoder]

cool stuff!

[@iflifewasmovie4766]

I was waiting to not start too soon and still see I am here in 10th lecture and it feels like a piece of cake this time....ALL THANKS TO YOU!! Waiting for all the videos..(DESPERATELY) ❤❤

[@human75788]

You are so good that I solved it in 1st attempt just thinking the right way which you taught us to do all these times. Thanks. I learned the whole graph from you.. for this question I watched only 1 minute of your video. haha!

[@vaishnavimore4860]

Thank you for making such great playlist!! Completely understood🚀

[@DPCODE72]

In 20:35, Striver was trying to say about The industry's requirements over the data. While teaching he wants to teach about everything that is required for a Company.

[@takeUforward]

Yes, in interviews they do care about these small things.

[@DPCODE72]

@@takeUforward While(1){ cout

[@Sp_Global-oc4tf]

@@DPCODE72 ; kon dega?

[@ujjawaltyagi8540]

understood !! Absolutely nailed the question (made it an easy cake walk )

[@adebisisheriff159]

Thanks so oooooooooooooooooooooooooooooooooooooooo much Striver. We love you!!!

[@cinime]

Understood! So awesome explanation as always. I guess this might one of the way to fill an area of one color with a different color in 2D field.... Anyway, thank you very much for your explanation!!

[@KratosProton]

Striver sir, can you please also cover LC 909. Snakes and Ladders in your playlist too, nobody on yt has explained this problem yet. Just a humble request

[@NaveenKumar-os8dv]

it seems easy when we see the video, but it is difficult when it comes to actually code, but I think I am getting better. It's really just the game of converting your "thinking into coding". If we can do this, we can solve any problem.

[@thatindianboy2817]

How do you ensure the resultant answer is minimum?

[@Harshanandita]

Based on the question, in 1 sec any rotten orange could rotten only its top-bottom or left-right neighbours So, it's simple step by step calculation, done using BFS

[@ashwanisharma8903]

@@thatindianboy2817 Bcz BFS is level order traversal. At each level we are keeping time as same. Same bcz when we dequeue one coordinate for all its four directions we will do +1 to value that was dequeued. So each level will have same time.

[@rahulsidhu5945]

Striver you are awesom, and that's why you are my inspiration. Thank you for everything🙂🙂

[@oqant0424]

Understood! So awesome explanation as always

[@kritikarawat2180]

Very easy explaination.Loved your explaination brother.

[@tasneemayham974]

THANK YOUUU STRIVERRR!!!! Python Code for those who need it: class Solution(object): def orangesRotting(self, grid): ROWS, COLS = len(grid), len(grid[0]) vis = [[0] * COLS for i in range(ROWS)] q = deque() cntFresh = 0 for i in range(ROWS): for j in range(COLS): if grid[i][j] == 2: q.append((i,j,0)) vis[i][j] = 2 if grid[i][j] == 1: cntFresh += 1 maxTime,cnt = 0,0 delRow = [-1,0,+1,0] delCol = [0,+1,0,-1] while q: r,c,t = q.popleft() maxTime = max(maxTime,t) for i in range(4): nRow = r + delRow[i] nCol = c + delCol[i] if nRow >= 0 and nRow < ROWS and nCol >= 0 and nCol < COLS and vis[nRow][nCol] == 0 and grid[nRow][nCol] == 1: vis[nRow][nCol] = 2 q.append((nRow,nCol,t+1)) cnt += 1 if cnt != cntFresh: return -1 return maxTime

[@shashank820]

Understood 🤓 10 lectures done. Waiting for next videos bhaiya 🙃

[@AryanGairola-th3qc]

understood done a very lengthy code because of you thankyou man...

[@FooBar-lb5wf]

Thanks, Striver. I can think of a couple of optimizations. First, we can avoid the last nested loop to check if all the fresh oranges are now rotten by just keeping two counters; freshcnt and rotcnt, with freshcnt representing the initial count of fresh oranges (can be counted in the initial nested loops) and rotcnt representing those fresh oranges which were rotten after coming in contact with rotten oranges (can be updated in the BFS logic when we update the visited array). If the two counts do not match, we can return -1. The second optimization is around the udpate of time t. We should be able to safely update t with the new value since BFS order would ensure that all the nodes with time 'ts' are processed before the nodes with time 'ts+1'. So the value of t should be monotonic in nature and so checking max(tm, t) may be redundant.

[@b_31mahammadzubair81]

Understood completely 🔥🔥 and waiting for the next video

[@sejalrai30]

pls jaldi jaldi laaiye graphs ke or lecture....you r the best explainer

[@priyanshkumariitd]

understood !! Wonderfully explained... Thanks Striver Bhaiya :)

[@Saurav_Kumar514]

Amazing explanation man! 🔥👌

[@gabru6809]

When would the whole series be uploaded? 😅

[@ManishKumar-zk5ky]

sir your explanation is very good Thank you🤩

[@shuvbhowmickbestin]

One thing, instead of creating a visited 2d matrix we can also take a set which stores pairs of coordinates visited already, that makes it easier to maintain.

[@subhranilsamanta2862]

Understood the whole Series.👏🏽

[@soumikpaul6503]

The best video to understand BFS

[@divyanshd5557]

it could have been done by the vector as well..just instead of vector vis it should be vector vis(n,vector(m,0))

[@nathonluke4058]

Understood. Also could i used queueq; data strucutre. Will it impact on Runtime Complexity or Space?

[@pratikdas1780]

UNDERSTOOD SIR. you're an angel.

[@srinivasjayaram570]

The best explanation ever !

[@rohitshrirame2378]

understood!!!! thanks for all of these!!!!!!

[@rishabhgupta9846]

understood,great explanation

[@anshumanbehera3706]

understood thanks for the amazing Explations

[@subhamoybera6456]

Great explanation 👍

[@Code_JAVA268]

Kudos to you striver highly recommended 🎉❤

[@1tav0]

awesome. thnk u striver understood

[@mohmedfaizrozdarsyed1234]

Thank you sir , Really appreciate your effort

[@stith_pragya]

Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@chitranshjain5075]

Completely UNDERSTOOD

[@ishangujarathi10]

amazing intuition!!! understood!!

[@sripriyapotnuru5839]

Thank you, Striver

[@ParasLeela]

it should be vis[nrow][ncol] = 2 instead of vis[nrow][ncol] = 1 otherwise we are never marking the fresh orange as rotten in the visited array

[@jonascharles1686]

Yep, he changed it later but didn't show that in video

[@rohitkumarpilania94]

can be done withput the visited array, just keep rotting the oranges in grid by marking them as 2

[@ankita7119]

but it is advised not to alter the question

[@amalkumar256]

This series is amazing sir

[@niranjanbhondave88]

I solved this question with a little bit of optimisation: while initialising queue, i maintained a fresh_count for number of fresh oranges. If grid[i][j] was 0 then visited[i][j] = 1, else if fresh orange then count++ else push in queue. each time i had a fresh orange, i marked visited ++ as well as count--. So to check for fresh oranges i didnt need another loop i just checked the count.If zero then only returned time else -1

[@vikasbagri1225]

understood it very will...

[@strickler453]

"understood" initially i thought : we can do without using extra space(true). but at the end : i got to know that don't lose the original input as company don't want to alter original data.

[@PrimeContent01]

understood this and all previous videos

[@pervejmia8240]

10 videos completed.. waiting for the next

[@amansinghal4663]

Just one correction bhaiya.... I think there was no need of using the max function for finding the time. Without it also the code gets accepted. You can find my AC below: class Solution { public: int bfs(queue&q, vector&visited, vector& grid, int rows, int columns){ int directions[5] = {0,-1,0,1,0}; int time=0; while(!q.empty()){ pairpr = q.front(); q.pop(); time = pr.second; for(int k=0; k=0 && nrow=0 && ncol

[@elizabethr5161]

Yes bro, you are right, since we use queue to store the time, there is no need of max variable.

[@viratrunmachine815]

you are truly legend sir

[@jatilyadav4000]

Best Explaination.....

[@shubhamyadav2623]

Just Amazing man !! I don't why all those idiots buys course if a guy like this giving us free !! We should support him for making such things free to us. Salute Striver🙋‍♀ good work bro!!

[@EngineerPlays2024]

Amazing vid man!

[@_hulk748]

Thankyou sir Understood 🙇‍♂❤🙏

[@zishan53]

Understood I watch it on your codeBeyond using node and submitted correctly

[@amanbhadani8840]

Hi bhaiya,can you tell me why you prefer to choose pairs in queue here,but in your old live classes you said that in interviews struct should be used due to its readibility.

[@it_08amanagarwal35]

Love the series bro ❤❤❤❤

[@shyren_more]

understood, thanks!

[@pranjalnama2420]

Thanks amazing explanation

[@DevashishJose]

understood,thank you.

[@shivayadav-po8un]

the major difference is when you see other tutorials, you can't write code until you see their code multiple times. In case of striver, his explanation is more than enough and our code just flows without even seeing striver's code. Take a bow#Striver

[@ajayjangid1164]

You are Great🎉🎉 Bhaiya.. ❤❤

[@sukritinarang5016]

Great Content !

[@systempesystm]

Loved This !!!

[@nishanthcodes4576]

understood!!!!!!!!!!!!!!!!!!!!! Thanks a lot

[@GeniuslyTensai]

waiting for further amazing content

[@anchalbudhrani572]

Quality content 🤩

[@Yash-uk8ib]

I think we do not have to maintain time at each step. Simplu counting levels in multisource bfs will do the job!

[@ranjithduraisamy6868]

Understood!! Thanks

[@madhabkafle8898]

I think you should also say, how is this question related to previous one for better analysis .

[@deepikasahu1592]

god level explanation!!

[@ANURAGSINGH-nl2ll]

understood thank you

[@amarjeetkumar-hk2jl]

Understood but please upload more videos as fast possible

[@aysams2]

Sir please make a video on - Find the maximum of minimums of every window size. It is hard and important, but you haven't made a video about it yet.

[@Amanjaisingh]

cannt we do dfs for 1 and find the nearsest 2 bhi pasing int h in function which take the count if we go more deep recursively

[@prashudeshmukh7902]

instead of pair........... we can use queue . keeping that aside ..amazing playlist bhaiya 👍👍

[@vishvaschoudhary3858]

or use queue q;

[@UECAshutoshKumar]

Thank you sir

[@VaibhavSingh-vy6gy]

Rotten Oranges felt like a piece of cake😂.... thnx to striver

[@harshkilaji1901]

Can we not instead find the nearest '2' or rotten orange for each '1' (fresh oranges) ?? And the answer would be the distance between farthest 2 and 1. If that '1' is unreachable we will automatically get -1. I guess we can also apply Dynamic programming to find subsequent distances.

[@aayushbisht4307]

18:19 no need for maximum tm = t will work

[@user-tk2vg5jt3l]

thank you Bhaiya

[@nasreensaba8484]

Hi I am new to DSA, I would like to request you make a comprehensive video explaining what topics should I do and in what order in Arrays, Strings, Stacks, Queues.. GFG is huge and i cant figure out what to do and leave.

[@takeUforward]

Coming tomorrow!

[@akash-alam]

Your are awesome man.

[@rahulsati5819]

awesome yr ................

[@herculean6748]

Thanks striver!!

[@CodeMode9313]

Its awesome bhai

[@dhyanprasad5611]

OP OP oP OP OP, this series is FIRE !!

[@morganyu3391]

Understood bhaiya

[@priyanshajmera3177]

Great explanation. But we don't need visited here so we can save some space.

[@akarshsachan21]

why we should take array instead of vector for the visited ?