Rotting Oranges
Vložit
- čas přidán 8. 07. 2024
- For business inquiries email partnerships@k2.codes SOCIAL
----------------------------------------------------------------------------------------------------------------
Instagram: / kevinnaughtonjr
Twitter: / kevinnaughtonjr
Patreon: / kevinnaughtonjr
GitHub: github.com/kdn251
MUSIC
----------------------------------------------------------------------------------------------------------------
xo bored llif3 by young frontwood
/ xo-bored-lif3 - Věda a technologie
2:01: **THROWS ROTTEN ORANGE**
if you guys need help with interview prep be sure to check out my tiers on Patreon prices are going to be going up soon due to demand and my limited time to give mock interviews etc.
patreon: www.patreon.com/KevinNaughtonJr
instagram: instagram.com/kevinnaughtonjr/
twitter: twitter.com/kevinnaughtonjr
Amazing work! Can you please do 5. Longest Palindromic substring using Manacher algorithm?
Thanks a ton!
@@swantanbarua9327 Thanks Swantan and I'll put it on my list!
Also, please include this video in your "leetcode easy" playlist. Your latest video "assign cookies" is there but not "rotten oranges". Thank You! 😄
Hey Kevin, question on the run-time of the algorithm. At the beginning you are traversing each row and column with 2 for loops in total that are nested. Wouldn't that mean this is at least an O(n*m) algorithm instead of O(n)? If we have a huge matrix with n rows and m columns, wouldn't that be O(n*m) ?
Kevin Could you please explain how run time complexity is O(n)
They should change the title of this question to COVID-19 spread
lol
I got the COVID-19 version of this question in an interview T.T
Multi-source BFS could have been a easier solution that could be solved in multiple other problems. :)
Thank you so much Kevin. I have been waiting for this question for a very long time and I even mentioned this in comments in one of your videos. Glad you made a video on this. ❤️❤️❤️
Anytime I hope it was helpful :)
I genuinely enjoy your videos. You have a very calming and clear way of communicating. Very very helpful for me. I was totally crapped out on that question on the Mock interview. But it was like my 10th that day so my brain was already mush. But now I feel like I know what I need to do.
I feel like this is one of those problems that if you have not seen before you will not be able to come up with an answer in time during the interview.
Great explanation, do you have a list of Amazon year 2020 questions? mind sharing,
Hey @Kevin ,
Could you please explain the leet code problem 1192 "Critical connections in a network"
Please can you say what is the time and space complexity for the solution?
Can you please , explain the directions how you come up with the direction coordinates
Would this work for matrix of size greater than 10 ?
Loving all these new videos coming out, current favourite binge channel
Thanks so much!!!
Just a quick note. You can improve the runtime by a few ms
when you remove every processed orange from rotten set.
At the end of the for (String s: rotten) loop, you can remove
this string from rotten, as it would just process the same orange again.
And we already know the result.
It sped up my Swift submission by like 50%
well, if you see.. he sets the rotten = infected.. and hence rotten will contain only the newly infected ones and discard the prev. bad ones. :)
Hi David, would be interested to see your solution if you still have it around, my swift solution comes up to 20 ms !
Why do you set rotten = infected at the end of the while loop?
Thanks for videos Kev, continue the upload streak!
anytime Sai and I will don't worry, have another video going live tonight at 9pm ET :)
Thanks Kevin for sharing it. I have 1 concern with this solution : If the matrix size is in 2 digit , lets say it is 10*12 , where the 10 is number of rows and 12 is the number of columns , then this line nextI or nextJ might not reflect the exact number of row/col. Instead of storing it in Hashset , if we can store the rotton oranages into 2 dimensional array in Queue , like Queue , then this limitation could be avoided. Thanks again for sharing it.
arup chakraborty yes you’re totally right that would be a better more extensible approach thanks for sharing :)
I was thinking the same thing when watching. My idea of solving it was saving each coordinate as:
"" + i + "_" + j
Or any other non-digit character between i and j to serve as a delimiter so that we know what is the row and what is the column value.
@@MetroCrunch Yes That's what I did
Great explanation! Where can I find the code used in the explanation?
At 7:43, are the directions for those coordinates correct? He mentions that {0,1} is moving down one cell, {1,0} is moving right, { -1,0} is moving left, and {0,-1} is moving up. Shouldn't it be {0,1} is moving right, {1,0} is moving down, {-1,0} is moving up, and {0,-1} is moving left?
I am glad that you did a video on this Kevin. Thanks. Same question, but with respect to infected servers was asked by Amazon to me in the initial round.
Anytime Nishad and interesting, how’d you do on that problem?
@@KevinNaughtonJr Similar one as yours using BFS with a queue though.
@@nishadkumar7322 ah nice
Brilliant solution and brilliant explanation!
Woah wonderfully explained 👏👏
Good explanation. thanks
Thanks for giving better solution 😊
Thank you Kevin!!!
Great solution! One small bug in the code : line 23 and 24 -> nextI should be direction[0] + i(current i) and nextJ should be direction[0] + j (current j)
Thanks for the video.
This problem is similar to the flood fills(leetcode.com/problems/flood-fill/), My question is BFS was not used in the flood fills but here. whether this problem can be solved by dfs ? Basically how to decide between bfs and dfs ?
keep the content coming kevin. doing gods work~ 🙏🙏
Thanks Tu!
Bruh where do u find your intro music?
soundcloud if you like the songs I link them in the description
Very Nice Explanation Kevin.....Keep posting like this...
Thanks Vineet and will do
Amazon loves all Things BFS during their Interviews! This one and Word Ladder are in their Top 10 most asked for sure!
So it seems!
Thanks so much for this lol! 🙏🏻🔥
There is actually (i think) a more efficient solution which only requires a constant number of passes through the 2 dim array.
first group all the oranges by their adjacencies : for example,
(0,1,X)
(0,1,1)
(X,0,0)
would make the top 3 1s and the one X in their own group (with the x being the rotten), and the X at the bottom in their own group. then return -1 if there is a fresh orange in its own grouping (ez case)
then, replace the coordinates for the fresh oranges by the distance to the nearest rotten orange in that group rounded up. for example:
1,X
1,1 becomes
1,X
2,1 because the distance from that bottom-left 1 to the x becomes 1.4 which rounds up to 2.
then just return the greatest number from each group returned.
Hey Man, great vid. Just a few changes which you can do to make the solution faster. Don't use maps that give amortized constant complexity use a queue instead for keeping track of rotten oranges. Don't keep track of fresh oranges you can derive those when traversing if the grid value of rotten is 2. The string is a huge time sink you can use Pair or an even faster integer array for storing the coordinates in the queue. These changes itself should speed up the solution by 50 % :)
In the direction two d array isn't {0,1} and {0,-1} means up and down respectively. no?
Hi Kevin,
Thanks for the explanation and solution. But this solution will not work for the cases where either row or column of the matrix goes beyond 9
Given N number of Strings, generate all combination of these String's characters, these Strings must be N long, and must contain only one number of char from each string.
example: "abc", "def", "ghi" --> adg, adh, adi, aeg ... cfg
Just one detail, but you can make it reasonably faster if instead of String you use Integer[]. Those conversions are killing your run time.
good call! Yeah strings are soooo expensive in Java
But how would you check existence of Integer[] in set ?
Edgard, Here's a JS version inspired by my memory of watching Kevin do this in Java, but where I couldn't remember why his had used a Set to track fresh oranges, so my derivation's implemented with original int indexes (not a string encoded key) against the original grid, when checking fresh oranges. Anyway, this is one option for optimizing it further, if an interviewer asks. leetcode.com/problems/rotting-oranges/discuss/1066098/JS-Solution-(tops-99.8-of-JS-submissions-on-runtime)-with-comments
Omg I was actually able to do it by myself before watching the solution!!!! 😄😄😄😄 (although I did get stuck and I had to get a brief session of brainstorming in the shower in order to solve it 😅).
This is a Medium now
Thanks Kevin!
Nidhi Singh anytime!
thats a lot of code but perfectly laid out , nice explaination
Pratik Kulkarni thanks!
I should not say this, because you help me a lot to overcome a lot of difficult problems, but I feel really happy when this 14:52 happens :D Thanks for making us learning and also entertain us XD
THis will not work. Because in BFS we choose only one source. But, at any one time, we can have multiple oranges as a starting point that are rotten. and all of them will start rotting at the same time. I had a different solution, BFS did not occur to me . But, my solution had n2 time complexity. Also another thing is that nextI and nextJ is always one of 0 or +/-1 so it will now show what are the correct coordinates in the grid. Am I missing something? PLease clarify
I was wondering if it would be better to just walk thru the whole structure and find the greatest distance from rotten to fresh. If you start at square 1 and count each square until you hit an end, then if that's greater than the greatest so far, store it as the greatest so far. Then slide the window to the next one and repeat. You can also use DP to determine if you've already counted a given path and skip over those. This should mean that you won't need more than one pass thru the whole set.
You inspires me all the time
Oh this one's an old video, i miss that whiteboard :(
Awesome
Time limit exceed!
Why can't we solve this question using the same approach as you taught us in the number of island problem.
I tried doing the same thing, but it didnt work. was just searching the same approach.
Solved it using the BFS approach. Looks cleaner and easier to understand
github.com/pankajrathi95/DS-Algo/blob/master/src/LeetCode/30DayLeetCodeChallenge-August2020/RottingOranges.cs
Because number of island problem won't give us the minimum time.
Thank you Kevin, I am currently preparing for my Google interview next month and your videos are really helping me 👍🏻👌🏻
Anytime! If you need help preparing be sure to check out my tiers on Patreon too: www.patreon.com/KevinNaughtonJr
good luck .
do you solve the questions beforehand or is it the first time in your videos?
I solve the questions beforehand
I think both techniques are good for people to learn. On my channel I solve leetcode questions live, if that's what you're interested in. :)
can anyone explain to me how the time complexity is O(n) ??
He is defining n in this case to be the total number of elements in a grid, but I think that's a little bit confusing. A better way to define this would be to say, assuming you are given a matrix of NxM size, the time complexity is O(mn). O(mn) is also the number of elements in the grid but thats because you define n as the number of rows and m as the number of columns, where as Kevin defined n as the total number of elements!
@@pengtroll6247 thanks for clarifying
When I first saw this question, I thought of doing it recursively as by looking at the pictures, you get a sense of if I'm a rotten orange, what other oranges can I rotten in the next minute. Then those oranges can ask the same question, etc. Then you just return the amount times you had to recurse. Of course, each orange could infect up to 4 other oranges, and you will still to do some housekeeping to make sure once an orange has been marked visited that no other orange would be able to visit it. Then at each level add + 1 minute (if you were able to rotten at least one orange) and return that back up the stack to the original infection orange(s) (will need to modify some logic for multiple starting rotten oranges if this can happen, but not much else). Just check to make sure the amount of visited oranges is == amount of oranges. If that is true return the amount of minutes else return 1.
Have you considered this fact?
Lets say you rot all possible oranges from one rotten one and mark them all visited(meaning you wont be rotting them further). In this process lets say one fresh orange took 5 sec to rot. But maybe it had one rotten orange right next to it. And it would have taken only 1 sec to rot. Now??
Heyo, can you also solve 01 Matrix question?
The grid width and height are not necessarily single digit. The charAt() - '0' trick may not work.
Who the hell makes this question an Easy Question? 😂
It's one of those problems that have a very simple solution to understand but conceiving it isn't easy.
Lc
Beautiful Explaination !
Two Key points I learned from this video:
1] 4 way direction traversal
2] Without parsing String you can convert it into Int beauty❤️
Thanks Sir!!
Respect ++
why dont we have boundary issues??
Because he's just using the direction as a string based key into a set, not as an index into the grid.
A similar optimized (JS) solution I wrote that used the original grid to check if fresh, rather than keeping a separate Set for the fresh oranges, had to check boundaries and not check row-1 if row==0 etc.
This is the zombie infection problem but with extra steps
good to know!
Absolutely love your explanations and videos, however this one went way over my head ( blame it on me being beginner leet coder/ dreaming to crack a FAANG interw(s). Wonder if such questions are asked even for QAE haha.Thank you for all the great content Kevin!
Priyanka Gokhale - Bapat anytime thank YOU for supporting me! If you need help learning this stuff from the beginning be sure to check out the interviewing service I created it’ll take you through a 12 week curriculum to make sure you’re familiar with the most common interview topics thedailybyte.dev/?ref=kevin
Can you be more clear on interviewing curriculum. I can see something on link, but can you be more clear on how to use it
fresh.add(" " + i + j) and rotten.add(" " + i + j )
can anyone explain this?
convert [i] [j] to string "ij"
cellular automata
Not related to this video, but can you make videos on system design as well please?
Anushree Acharjee hoping to start making them soon!
Hi Kevin,
Thanks for the solution, greatly appreciate it. Can you explain how the int[][] directions = {{0,1},{0,-1},{-1,0},{1,0}}; part works? and how did you traverse directions using for(int[] direction : directions){ int nextI = i + direction[0];
int nextJ = j + direction[1];how you decide if its left right, up and down?
Thank you.
the first number in each of the represents the change we're making to our current row and the second number represents the change we're making to our current column, hope that helps!
@@KevinNaughtonJr did you forget to add i & j to nextI and nextJ respectively? Or am i missing anything?
@@poorvak7867 He did forget and when he ran it he got the wrong answer. So he edited it and added the i+ and j+.
Yes sir it was helpful
Thank you for the great explanation! I think the space complexity should be O(n2) since we have populated the two initial hash-sets using a nested for loop of worst case size n. Correct me if I get it wrong.
Its BFS to traverse only fresh oranges, every BFS traversal you rot the fresh tomatoes. So its NOT O(n2)
@Merry. you are right space complexity is O(N) where N is number of cells in grid or O (M*N) where M and N are dimensions of the grid. Both are same .
This was pretty similar to how Corona virus is spreading... :( So sad... But thank you for showing us this great video.
I don't know why there are two scu****s clicked the dislike button. Thanks for sharing this, Kevin! you're awesome!
it's all good there will always be people who will dislike vids so don't sweat it and anytime Mohammed :)
Hi Kevin, Hey you are doing great job , i love your videos and explaining process are awesome. Thanks for this. Need a favor about one question , ie. 3 sum questions...int[] A = { 0,10,15,20,25} , sum = 8, could you explain me if we add three numbers from array exact value else closest meet values for this sum. print what are the values . Kindly let me know about this. Thanks in advance.
Anytime! Try to think about the "brute force" solution O(N^3) and then try to optimize. If you need help with problems/interviews check out the tiers on my Patreon page: www.patreon.com/KevinNaughtonJr
🍊
very appropriate for this vid
Now this problem is upgraded to Medium :P
Thanks a lot :). Another crucial request: 1192. Critical Connections in a Network
No problem :) and I’ll add that problem to my list!
The Algorithm to solve that one efficiently is Quite Hard to implement, let alone in an Interview setting, I'm still not sure why they ask this ridiculous Question. Having said that, you can do a brute force if the Graph is reasonable small, remove one node at a time and do a DFS.
@@jlecampana unfortunately this is the world of interviews atm :(
I was surprised to see this one so high up on the LeetCode list. I doubt the majority of people would get this one.
This is just too creative for me. Ill stick to using queues lol.
i think nextI = direction[0] + i;
nextj = direction[1] + j;
I think so too, cause you don’t check the directions in magnitude of 1 every loop.
In Line no. 36: Shouldn't it be rotten+= infected; As we are updating rotten with newly infected.
We only care about newly rotten oranges since an orange infects all of its neighbors as soon as it is rotten.
Old rotten oranges can't infect any more oranges moving forward since their own reach has been exhausted.
That's why it makes sense to consider the newly infected as the relevant rotten oranges each iteration, after the first.
For the first time, your solution seems hard to understand for me. Anyway, I love your all videos though. Thanks.
aw man sorry Alper :( thanks though!
A clean solution and less confusing can be found at : leetcode.com/problems/rotting-oranges/discuss/491183/Simple-Java-Queue-Solution-Clean-Code
You tracked oranges using Hash-table, but the question doesn't ask you to tell the position of oranges. Why not just use the SUM of fresh oranges? You can subtract by 1 each time when you rotten a fresh orange. At the end of program, if the sum == 0, then return the time elapsed, otherwise return -1 because there is still fresh oranges not being rottenned yet.
Hey Kevin
Is there your telegram channel?
Is this bFS?
GOT IT!!
NICE
What dose bfs stand for? This problem reminded me of pathfinding algorithms and graph theory.
its a method of traversing graph or tree
breadth first search. It starts with a root, then search its neighbor from left to right, then search neighbor's neighbors... goes on.
So Leetcode premium user 😏
Cool code!!!
Once again won my heart 💕
Nice Explanation.A small change can port the same code if rows and columns are greater than or equal to 10
public int orangesRotting(int[][] grid) {
Set fresh = new LinkedHashSet();
Set rotten = new LinkedHashSet();
for(int i=0;i0){
return -1;
}
rotten = infected;
minutes++;
}
return minutes;
}
Hope this might help some one.
Hi can you solve Super Egg Drop problem
*BFS will be much faster*
Hi, could you help me figure out why my solution doesn't work. It's passes the initial test but does not change the values of the grid.
Thanks for these vids btw!
public int orangesRotting(int[][] grid) {
//need adjacency list/matrix
Queue q = new LinkedList();
int[] count = new int[1];
count[0] = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
if(grid[i][j] == 2) {
q.add("" + i + j);
bfs(grid, i, j, count, q);
}
}
}
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
System.out.println(grid[i][j]);
// if(grid[i][j] == 1) {
// return -1;
// }
}
}
return count[0];
}
private static void bfs(int[][] grid, int i, int j, int[] count, Queue q) {
while(!q.isEmpty()) {
String s = q.remove();
//System.out.println(s);
i = Integer.parseInt(s.substring(0,1));
j = Integer.parseInt(s.substring(1));
if(i - 1 > 0 && grid[i - 1][j] == 1) {
count[0]++;
i--;
grid[i][j] = 2;
q.add("" + i + j);
}
if(i + 1 < grid.length && grid[i + 1][j] == 1) {
count[0]++;
i++;
grid[i][j] = 2;
q.add("" + i + j);
}
if(j - 1 > 0 && grid[i][j - 1] == 1) {
count[0]++;
j--;
grid[i][j] = 2;
q.add("" + i + j);
}
if(j + 1 < grid[i].length && grid[i][j + 1] == 1) {
count[0]++;
j++;
grid[i][j] = 2;
q.add("" + i + j);
}
}
}
}
Definitely not easy😐
Shishir Aithal agreed
Why you doing easy questions? Go for medium-hard ones.
this question is labeled as "easy" but I don't necessarily think it should be. I don't think the labels on LeetCode mean much tbh
kevin is getting thinner, I'm worried.
I appreciate the concern, but don't be worried about me I'm good! I've been pretty consistent in the gym and I think I'm actually gaining muscle (and therefore weight) despite what it might look like on camera haha
Thanks, Kevin. It's very helpful. Here is my Python3 version github.com/abushoeb/leetcode/blob/master/994-rotting-oranges.ipynb for your solution.
this is O(n^3) solution there are other much efficient solutions for this question
Bro be regular in uploading such videos
what the hell..... till now you just reached the easy level question
try to challenge yourself and consider difficult questions as well
🍊
orange you guys glad I did this problem?