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

GfG-Problem Link: bit.ly/3oekoir
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
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.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

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

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

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

[@snehachauhan9421]

Thank you so much striver, your graph and dp playlist are really really so good. After jumping from one video to another, one blog to another and endless loop. Your playlist was my saviour, I cleared all the concepts at once and now they're fixed in my head. Not only this your a-z sde sheet helped me a lot to crack interview at big pbc. Thanks a lot. You're literally GOAT of DSA

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

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

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

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

[@loser0023]

😂 😂 ​@@Sp_Global-oc4tf

[@SatyaMantha]

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

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

[@RohitKumar-dz8dh]

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

[@suheabkhan2546]

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

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

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

[@vaibhavagarwal2421]

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

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

[@vaibhavsapate9168]

Truly powerful explanations I just watched the video till 10:00 and implemented code by myself.

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

[@AdityaMaurya-dw3od]

Striver teaches so great that I was able to solve this question on my own with a slightly different approach.

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

[@prashudeshmukh7902]

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

[@vishvaschoudhary3858]

or use queue q;

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

[@facttecher3039]

Hey Striver, You given me the hope to take my carrer forward😊😊. Thanks bro❤❤

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

[@shashank820]

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

[@abhinavsingh8090]

we can use vector to store visited matrix instead of vectorvis it will be vectorvis(n, vector(m,0));

[@rajavignesh7216]

Both are same right

[@cursed_nerd]

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

[@adebisisheriff159]

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

[@gabru6809]

When would the whole series be uploaded? 😅

[@soumikpaul6503]

The best video to understand BFS

[@googleit2490]

Graph Revision: Done and dusted in Graph Revisiion (BFS) (10 mins) Nov'24, 2023 11:27 pm

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

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

[@sejalrai30]

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

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

[@anshpradhan1954]

This guy will rotten this ❌ This guy will ROT this ✅ love your content Sir

[@codewariors]

very easy to understand . hats off strivers

[@rahulsidhu5945]

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

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

[@manjitha24]

your explanation is so beautiful, soo elegant .. just like a woooww woowww🤩

[@shaikfahim1232]

class Solution { public: //Function to find minimum time required to rot all oranges. int orangesRotting(vector& grid) { // Code here vector ans=grid; int n=ans.size(); int m=ans[0].size(); queue q; for(int i=0;i

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

[@priyanshajmera3177]

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

[@ujjawaltyagi8540]

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

[@pratikdas1780]

UNDERSTOOD SIR. you're an angel.

[@ManishKumar-zk5ky]

sir your explanation is very good Thank you🤩

[@afuadajoemmanuel5735]

Thanks for all you do Striver 🙏

[@vaishnavimore4860]

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

[@AryanGairola-th3qc]

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

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

[@iamnottech8918]

if someone is confused by the code here is the simpler version class Solution { public: int orangesRotting(vector& grid) { int n=grid.size();//rows int m=grid[0].size(); //columns queue q; // {{2,3},1} int visited[n][m]; for(int i=0;i

[@VaibhavSingh-vy6gy]

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

[@pervejmia8240]

10 videos completed.. waiting for the next

[@apmotivationakashparmar722]

Thank you so much Striver!

[@priyanshkumar17]

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

[@chitranshjain5075]

Completely UNDERSTOOD

[@knox9450]

18:14 at this instead of 1 it should be 2 as we marking it rotten in vis array

[@oqant0424]

Understood! So awesome explanation as always

[@subhranilsamanta2862]

Understood the whole Series.👏🏽

[@tasneemahmad7858]

Code of the Video:- . . . . . . . #include using namespace std; int orangesRotting(vector &grid) { int n = grid.size(); int m = grid[0].size(); queue q; int vis[n][m]; int cntfresh = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 2) { q.push({{i, j}, 0}); vis[i][j] = 2; } else { vis[i][j] = 0; } if (grid[i][j] == 1) cntfresh++; } } int tm = 0; int drow[] = {-1, 0, 1, 0}; int dcol[] = {0, 1, 0, -1}; int cnt = 0; while (!q.empty()) { int r = q.front().first.first; int c = q.front().first.second; int t = q.front().second; tm = max(tm, t); q.pop(); for (int i = 0; i < 4; i++) { int nrow = r + drow[i]; int ncol = c + dcol[i]; if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && vis[nrow][ncol] != 2 && grid[nrow][ncol] == 1) { q.push({{nrow, ncol}, t + 1}); vis[nrow][ncol] = 2; cnt++; } } } if (cnt != cntfresh) return -1; return tm; } int main() { vector grid = {{0, 1, 2}, {0, 1, 2}, {2, 1, 1}}; cout

[@pranavm002]

this is incorrect solution! the check inside the for loop is incorrect. It should be "vis[nrow][ncol] == 0" and not "vis[nrow][ncol] != 2". In the video strive show " vis[nrow][ncol] != 2" but before submission he changed it to "vis[nrow][ncol] == 0".

[@nathonluke4058]

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

[@kritikarawat2180]

Very easy explaination.Loved your explaination brother.

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

[@dhyanprasad5611]

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

[@zishan53]

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

[@sripriyapotnuru5839]

Thank you, Striver

[@Saurav_Kumar514]

Amazing explanation man! 🔥👌

[@pcgaming6597]

For java people Code : public static class pair{ int first; int second; pair(int first,int second){ this.first=first; this.second=second; } } public int orangesRotting(int[][] grid) { int n=grid.length; int m=grid[0].length; int time=0; Queue q = new LinkedList(); for(int i=0;i

[@Code_JAVA268]

Kudos to you striver highly recommended 🎉❤

[@mohmedfaizrozdarsyed1234]

Thank you sir , Really appreciate your effort

[@tusharkumarroy-tj2qg]

understood 70 percent

[@subhamoybera6456]

Great explanation 👍

[@aayushbisht4307]

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

[@viratrunmachine815]

you are truly legend sir

[@srinivasjayaram570]

The best explanation ever !

[@Yash-uk8ib]

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

[@stith_pragya]

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

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

[@PrimeContent01]

understood this and all previous videos

[@KUMARSAURABH-s5i]

Understood Striver!!

[@kuberarale1454]

Two days before, this question was asked to me in Amazon SDE Intern Interview and i messed up!

[@amalkumar256]

This series is amazing sir

[@pranjalnama2420]

Thanks amazing explanation

[@jatilyadav4000]

Best Explaination.....

[@b_31mahammadzubair81]

Understood completely 🔥🔥 and waiting for the next video

[@ajayjangid1164]

You are Great🎉🎉 Bhaiya.. ❤❤

[@gangsta_coder_12]

Understood ✌✌

[@_hulk748]

Thankyou sir Understood 🙇‍♂❤🙏

[@UECAshutoshKumar]

Thank you sir

[@saumilaggarwal5233]

thnx, but we can also do this question without visited 2D vector code: class Solution { public: int orangesRotting(vector& grid) { int m= grid.size(); int n= grid[0].size(); int tm=0; queue q; for(int i=0;i

[@rahulkapoor7305]

Yes, as we are changing values to 2 from 1, so a check on this will take care of is visited or not as well.

[@thatindianboy2817]

Why not DFS? If we can use, why didn't we? Pros and Cons, DFS vs BFS in the current question? How are we sure it will ensure that it will be the minimum time? What is the intuition behind making the decisions you made? These are the questions expected from a video honestly. Might sound silly but someone who comes this far is looking for them. Reciting the question and the solution verbatim from a solved article doesn't really help much. Gives the impression of "Mug it till you make it". The most challenging part to solve a question is to understand it and the inner complexities which are clearly ignored here.

[@RajivChatterjee]

We can use dfs as well but we will have to set an offset of 2 or greater than 2 so that the values 0( for no orange) and 1( For fresh orange) doesnt interfere with the value of time taken we put in the grid. Here's the code for it. class Solution { public int orangesRotting(int[][] grid) { if(grid == null || grid.length == 0) return -1; int n=grid.length; int m=grid[0].length; for(int i=0;i

[@PreyumKumar]

We can change 1 to 3 so that will not destroy the data to irrevertible changes.

[@1tav0]

awesome. thnk u striver understood

[@vikasbagri1225]

understood it very will...

[@AbhayKumar-gl5hh]

I understood the concept but I have a question, we chose to take a max of the time(i.e tm=max(tm,t)) but I cant think of any test case in which if we apply to get correct answer if we don't take max of time inside the BFS, BFS automatically takes care of finding of the minimum possible time to rot all apples so why bother to take the max? I tried to run the code without the taking max of time and it worked. I might be missing something here if I'm please help.

[@subhamoyburman3093]

I also think so, I even put it in gpt to give me TC which would violate this it did not provide anything valid.

[@amarjeetkumar-hk2jl]

Understood but please upload more videos as fast possible

[@NODEZEN-s8e]

Also I guess you don't need tm=max(tm,t) as in BFS when you have rotten one fresh orange its time has been increased by level 1 and if you are rotting by that orange than count will increase but ya you need to change grid[i][j] to 2 when you are putting in queue which might not be good for you as you are changing input .

[@DurgaSivaLokeshTelaprolu]

My Approach: class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) visited = [[None for _ in range(n)] for _ in range(m)] q = deque() for i in range(m): for j in range(n): if grid[i][j] == 2: q.append([[i, j],0]) visited[i][j] = 2 res = 0 while q: (r, c), time = q.popleft() res = max(res, time) for nr, nc in [(r , c - 1), (r, c + 1), (r + 1, c), (r - 1, c)]: if (0

[@PenAndSpecs007]

Amazing vid man!