G-10. Rotten Oranges | C++ | Java
Vložit
- čas přidán 8. 09. 2024
- 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...
---------------------------------------------------------------------------------------------------------------------------
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
Don't have an account in Instagram
and it distracts me much more than anyone does 😎😎😎
Understood
I am yet to start Tree and Graph, should start graph first? or do I need to do tree first?
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
where is java code I am unable to find
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
😂😂😂
Agreed bro
Agree
@@monumishra9638 hey guys , how far your preparation came
@@vishakhas1867 how far
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.
Yes, true, I agree
@@takeUforward which tool do you use to explain? it is so good !
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];
Anything is fine make sure the coordinates traverse all those direction that's it... Btw good thinking
cool stuff!
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.
Yes, in interviews they do care about these small things.
@@takeUforward While(1){
cout
@@DPCODE72 ; kon dega?
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.
How do you ensure the resultant answer is minimum?
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
@@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.
it could have been done by the vector as well..just instead of vector vis it should be vector vis(n,vector(m,0))
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
Striver, I like the way you make toughest problems look so easy with your explanation. Kudos to you!
When would the whole series be uploaded? 😅
instead of using pair we can use vis grid to store the time as well
For sure no one need to worry about code in any language after getting approach how to tackle problem 😊. Thanks again .
understood bahut chota compliment hai.... Dil khush hojata hai aap say padke bhai
can be done withput the visited array, just keep rotting the oranges in grid by marking them as 2
but it is advised not to alter the question
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!!!!!!!!
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) ❤❤
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.
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
Yes bro, you are right, since we use queue to store the time, there is no need of max variable.
Understood 🤓
10 lectures done. Waiting for next videos bhaiya 🙃
we can use vector to store visited matrix instead of vectorvis it will be vectorvis(n, vector(m,0));
very easy to understand . hats off strivers
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
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
Yep, he changed it later but didn't show that in video
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 .
instead of pair........... we can use queue .
keeping that aside ..amazing playlist bhaiya 👍👍
or use queue q;
your explanation is so beautiful, soo elegant .. just like a woooww woowww🤩
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
Though striver explains approach very well, there can be improvements to code.
Beginners/college students may be happy with such code, as it solves the problem.
But it soon becomes a habit to just focus on working code and readability is not given due importance.
Interviewers with a few years of industry experience, may find such code annoying.
So when you solve the problem also think what names can convey the logic clearly. Clarity in thinking will reflect in code too.
One improvement is : some names have to be meaningful
1. Instead of Pair class - the class could have had a meaningful name like RottenOrange class , with row, column and time at which it got rotten. (or even an Orange with more attributes)
So we will be adding RottenOranges into the queue. That is what is central idea right processing the rotten oranges. (Pair here was absolutely inappropriate as we are storing 3 attributes)
First add the initial rotten oranges into the Queue .
Later do a BFS - while queue is not empty - pop a rotten orange and check if any of the neighbouring slots have a fresh orange which is not visited yet. If yes, then make it rotten and add it to the queue of rotten oranges.
2. Also a method can be added like: computeNeighbouringSlot and checkValidityOfNeighbouringSlot(nrow, ncol) instead of having complex computations. We need to abstract them to methods with clear names to understand the main logic.
Such improvements can greatly add readability to code (basic requirement of a software engineer) and will abstract the implementations so that the reader doesnt have to strain to understand the logic.
Graph Revision:
Done and dusted in Graph Revisiion (BFS)
(10 mins)
Nov'24, 2023 11:27 pm
Thanks so oooooooooooooooooooooooooooooooooooooooo much Striver. We love you!!!
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
understood
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.
pls jaldi jaldi laaiye graphs ke or lecture....you r the best explainer
18:14 at this instead of 1 it should be 2 as we marking it rotten in vis array
"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.
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!
sir your explanation is very good Thank you🤩
understood done a very lengthy code because of you
thankyou man...
Thanks for all you do Striver 🙏
The best video to understand BFS
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.
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!!
Rotten Oranges felt like a piece of cake😂.... thnx to striver
Striver you are awesom, and that's why you are my inspiration. Thank you for everything🙂🙂
Great explanation.
But we don't need visited here so we can save some space.
understood !!
Absolutely nailed the question (made it an easy cake walk )
Thank you for making such great playlist!! Completely understood🚀
OP OP oP OP OP, this series is FIRE !!
Understood
✌✌
understood !! Wonderfully explained... Thanks Striver Bhaiya :)
10 videos completed.. waiting for the next
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.
I also think so, I even put it in gpt to give me TC which would violate this it did not provide anything valid.
Understood. Also could i used queueq; data strucutre. Will it impact on Runtime Complexity or Space?
I think we do not have to maintain time at each step. Simplu counting levels in multisource bfs will do the job!
Understood
I watch it on your codeBeyond using node and submitted correctly
understood 70 percent
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.
Coming tomorrow!
Understood! So awesome explanation as always
Amazing explanation man! 🔥👌
UNDERSTOOD SIR. you're an angel.
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 .
Loved This !!!
Very easy explaination.Loved your explaination brother.
18:19 no need for maximum tm = t will work
Great explanation 👍
Understood the whole Series.👏🏽
did by myself
Kudos to you striver highly recommended 🎉❤
Understood Striver!!
Thank you sir , Really appreciate your effort
Amazing vid man!
Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
hi striver i know you are busy, But pls make a video on how to make notes for your sde sheet and how to use the sheet effectivity.
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
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.
Thank you sir
18:11 vis[nrow][ncol] should be equal to 2;
STRIVER GOAT🤘🤘
Thank you, Striver
Completely UNDERSTOOD
At 18:13 it should be vis[nrow][ncol] = 2; instead of vis[nrow][ncol] = 2;
Understood
Understood.
Understood completely 🔥🔥 and waiting for the next video
Understood!
understood this and all previous videos
Two days before, this question was asked to me in Amazon SDE Intern Interview and i messed up!
The best explanation ever !
understood!!!! thanks for all of these!!!!!!
thank you Bhaiya
you are truly legend sir
Understood 😊
Understood but please upload more videos as fast possible
amazing intuition!!! understood!!
awesome. thnk u striver understood
Thanks amazing explanation
understood,great explanation
understood thanks for the amazing Explations
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!!
second O(N*M*4) is for all rotten oranges in the queue right?