If you need help with anything feel free to shoot me a message on Instagram or scope my Patreon to join the Discord server (links are in the description)!
Kevin Naughton Jr. Would it be possible to replace this video with an alternate one with efficient solution which is BFS? Please consider the time complexity of this dfs solution. It’s terribly slow. After all, interviewers expect the candidates to provide efficient solution at the interview. When shortest path is mentioned in this, I wonder why you skipped any shortest path finding algorithm to solve it. Thank you.
@@darod6098 For BFS, if you seed the queue with all gate cells, you then only have to visit every cell at most once, for a worst-case runtime of O(R*C), for row-count R and col-count C. With a sufficiently unlucky testcase it seems like the DFS algorithm presented in the video could flood-fill the entire space many times. At least once per gate, but probably even multiple times from a single gate, so long as every time it overwrites the cells with slightly lower values.
Thank you, Kevin. Thumbs up as usual. Small addition to enhance understanding: rooms[i][j] < count - the MOST IMPORTANT check also because it covers walls as well, i.e. cells with value -1. Those cells will NOT be updated because their value is ALWAYS < count
@@adrianfiedler3520 I'm still confused about a detail. If we don't *return;* when we encounter a -1, won't it count it like an empty cell for the purposes of iteration? Wouldn't an empty cell record the distance to the closest gate, _including_ through a wall? Or, put another way, if you had a room fully closed off by walls with no gate within, won't that room still fill with distances to the nearest (outside) gate? I think including the condition *rooms[col][row] == -1* for the first *return;* statement would cover this.
@@AstroTibs naah...that won't be filled...because for any gates outside this region you said, as we start the recursion from the gate we will always stop and return the recursion from the wall as its value which is -1, is always less than any number >=0.
I think BFS is already optimized for this question. With DFS, you will have to check if the distances calcualted is better than any previous distance. This would not be the case with BFS.
Thanks! It works. But I am a little confused. These different if conditions look like the same meaning as the if condition at the beginning (which then return; )
Kevin is the best. He explains the logic and writes the code too. I really appreciate your hard work Kevin. Please keep making these videos. O feel if I would have seen your videos before my Microsoft interview then probably I might have got a job offer
Hi Kevin, First of all your'e super awesome. Your'e videos really helped allot to get FAANG offers :) This specific video needs to be updates as you will get a TLE using this algorithm. This basically needs to be a BFS which runs on queue which runs on queue once all cords with 0 have been set on the queue.
One thing: It is just a coincidence this works as all the test case cells can reach a gate. There is no "inserting INF" in your solution, unlike what the Leetcode stipulates. That said, if the test cases do not cover that possibility, that is not your problem. Good video, obviously.
if (board[row][col] < distance) return (this check is combined with out of bounds check); We start with distance = 0, and wall = -1, so walls are implicitly ignored!
The problem is designed to represent 'Gates' as 0 and 'Walls' as 1, so while matrix[i][j] = count overwrite the original starting dfs location, count will always be 0, thus no net change; if Gates were 'G' and Walls were 'W', then we can introduce additional if checks to respond appropriately.
Kevin, great explanation! I have trouble understanding weather to use dfs or bfs in these kind of problems. Whenever I hear shortest distance I tend to use BFS but in this problem using DFS we got the same result, how to figure out if a problem is well suited for BFS or DFS? Is it like BFS is more suited for shortest distance to one destination and DFS for all pair shortest distance?
Hey Nitish, yeah it can be tricky trying to pick bfs or dfs. Generally speaking when you're trying to find the shortest path from point A to point B you should opt to use BFS (assuming all edge weights are 1) , it'll help ensure that you don't go down any crazy rabbit hole like you can in DFS. So, in retrospect, although the runtimes don't differ in the worst case, it probably would've been best to use BFS in this problem
@@KevinNaughtonJr Isn't the worst-case runtime complexity better for BFS though? You seed the queue with all gate cells, and then you only have to visit every cell at most once, for a worst-case runtime of O(R*C), for row-count R and col-count C. With an unlucky testcase it seems like your DFS algorithm could flood-fill the entire space many times. At least once per gate, but probably even multiple times from a single gate, so long as every time you overwrite the cells with slightly lower values.
I enjoy your videos brother. Let N,M be the number of nodes, edges in a general graph. This problem can be solved in M+Nlog(N) time in a fashion similar to Dijkstra. Your algorithm runs in N(N+M) time. In our case M=O(N) --> Nlog(N) vs N^2
What's the difference between adding to count parameter in dfs function call and incrementing count in the processing prior to that? And why doesnt the solution return the board? Is this stated in the problem?
really nice explanation ! one suggestion is if you could use animations to explain the solution , that could really help us to understand in much better way .
We can solve it using multisource BFS in a very optimal way. Just add all the gates into the queue and keep on traversing level by level keeping the track of the visited cells. It can be solved in O(n*m) time complexity.
Aravindh Saai Ravichandran anytime! Check out the interviewing service I made if you need help with understanding problems like this thedailybyte.dev/?ref=kevin I’d join a premium plan if you can!
Could you explain why the time complexity is O(m*n) for this one? I understand that we are traversing through the entire grid which is m*n but do we not consider the recursive calls of dfs?
hard to say because it depends on comfortable you are with these questions and topics. If you need help preparing for these interviews I'd suggest signing up for the interviewing service I created thedailybyte.dev/?ref=kevin I'd join the annual plan if you can!
If you need help with anything feel free to shoot me a message on Instagram or scope my Patreon to join the Discord server (links are in the description)!
Kevin Naughton Jr. Would it be possible to replace this video with an alternate one with efficient solution which is BFS? Please consider the time complexity of this dfs solution. It’s terribly slow.
After all, interviewers expect the candidates to provide efficient solution at the interview. When shortest path is mentioned in this, I wonder why you skipped any shortest path finding algorithm to solve it.
Thank you.
@@algorithmimplementer415 Why do you think that time complexity of this solution is worse than a bfs solution?
@@darod6098 For BFS, if you seed the queue with all gate cells, you then only have to visit every cell at most once, for a worst-case runtime of O(R*C), for row-count R and col-count C.
With a sufficiently unlucky testcase it seems like the DFS algorithm presented in the video could flood-fill the entire space many times. At least once per gate, but probably even multiple times from a single gate, so long as every time it overwrites the cells with slightly lower values.
Hi Kevin, Thank you for your video. Can you please show a BFS solution of this problem?
Kevin, why you did not detect circle and avoid around situation?
Thank you, Kevin. Thumbs up as usual.
Small addition to enhance understanding:
rooms[i][j] < count - the MOST IMPORTANT check also because it covers walls as well, i.e. cells with value -1. Those cells will NOT be updated because their value is ALWAYS < count
Ah right, I wondered why no check if it is a wall with -1. But of course, it is always < count.
@@adrianfiedler3520 I'm still confused about a detail. If we don't *return;* when we encounter a -1, won't it count it like an empty cell for the purposes of iteration? Wouldn't an empty cell record the distance to the closest gate, _including_ through a wall?
Or, put another way, if you had a room fully closed off by walls with no gate within, won't that room still fill with distances to the nearest (outside) gate?
I think including the condition *rooms[col][row] == -1* for the first *return;* statement would cover this.
@@AstroTibs naah...that won't be filled...because for any gates outside this region you said, as we start the recursion from the gate we will always stop and return the recursion from the wall as its value which is -1, is always less than any number >=0.
I think BFS is already optimized for this question. With DFS, you will have to check if the distances calcualted is better than any previous distance. This would not be the case with BFS.
Sheez I watch all your videos except this..., this was my interview question :(
I must thank you as when I watch your videos I feel confident about coding before the interview. :) Please keep on uploading more videos. :)
This solution seems no longer working, it's going to time out. Need to add some condition when doing dfs like this:
if(r < rooms.length - 1 && count+1 < rooms[r+1][c]){
dfs(r+1, c, count+1, rooms);
}
if(r > 0 && count+1 < rooms[r-1][c]){
dfs(r-1, c, count+1, rooms);
}
if(c < rooms[r].length-1 && count+1 < rooms[r][c+1]){
dfs(r, c+1, count+1, rooms);
}
if(c > 0 && count+1 < rooms[r][c-1]){
dfs(r, c-1, count+1, rooms);
}
Great fix!
Thanks! It works. But I am a little confused. These different if conditions look like the same meaning as the if condition at the beginning (which then return; )
Kevin is the best. He explains the logic and writes the code too. I really appreciate your hard work Kevin. Please keep making these videos. O feel if I would have seen your videos before my Microsoft interview then probably I might have got a job offer
Hi Kevin,
First of all your'e super awesome. Your'e videos really helped allot to get FAANG offers :)
This specific video needs to be updates as you will get a TLE using this algorithm.
This basically needs to be a BFS which runs on queue which runs on queue once all cords with 0 have been set on the queue.
This solution rechecks nodes multiple times. If you BFS every gate simultaneously, you only have to update a node once.
you're the man. this solution is simpler than the results I've seen in the LC discussion board (for JS).
One thing: It is just a coincidence this works as all the test case cells can reach a gate. There is no "inserting INF" in your solution, unlike what the Leetcode stipulates. That said, if the test cases do not cover that possibility, that is not your problem. Good video, obviously.
By the way, anyone know how to turn off the annoying Algoexpert girl?
I think you don't have to insert INF, as they are already initialized with INF. So I you can't reach it, it will still be INF and should work.
how come it's not considering the -1(walls). Meaning how come we didn't check anything related to -1 here? Can someone please explain?
if (board[row][col] < distance) return (this check is combined with out of bounds check); We start with distance = 0, and wall = -1, so walls are implicitly ignored!
@@0anant0 Thanks man that's smart not sure if he mentioned it in the video
room[i][j]< count is one of the conditions where the dfs returns. count will always be greater than -1.
The problem is designed to represent 'Gates' as 0 and 'Walls' as 1, so while matrix[i][j] = count overwrite the original starting dfs location, count will always be 0, thus no net change; if Gates were 'G' and Walls were 'W', then we can introduce additional if checks to respond appropriately.
Yeah he didn’t mention it but the out of bounds check covered it
Thanks a ton! Keep up the great work!
Some more similar dfs problems on leetcode:
Number of Islands
Maximum Area of Island
Battleships on a board
Anytime and will do!
They asked the spiral matrix question recently. I was stumped but still did it more or less.
Nice!!!
Kevin, great explanation! I have trouble understanding weather to use dfs or bfs in these kind of problems. Whenever I hear shortest distance I tend to use BFS but in this problem using DFS we got the same result, how to figure out if a problem is well suited for BFS or DFS? Is it like BFS is more suited for shortest distance to one destination and DFS for all pair shortest distance?
Hey Nitish, yeah it can be tricky trying to pick bfs or dfs. Generally speaking when you're trying to find the shortest path from point A to point B you should opt to use BFS (assuming all edge weights are 1) , it'll help ensure that you don't go down any crazy rabbit hole like you can in DFS. So, in retrospect, although the runtimes don't differ in the worst case, it probably would've been best to use BFS in this problem
@@KevinNaughtonJr Isn't the worst-case runtime complexity better for BFS though? You seed the queue with all gate cells, and then you only have to visit every cell at most once, for a worst-case runtime of O(R*C), for row-count R and col-count C.
With an unlucky testcase it seems like your DFS algorithm could flood-fill the entire space many times. At least once per gate, but probably even multiple times from a single gate, so long as every time you overwrite the cells with slightly lower values.
Multi BFS works here aswell.
@@mhelvens
That's what's called multi-source BFS
It's short and concise. Thanks for teaching.
Anytime, I hope it was helpful!
This code gives TLE now
Where do you get these crazy into musics from from?
It's such a clean and easy to understand solution, but now it gives TLE (June 7th 2022).
I was reading this in leet code and had trouble understanding. But this video really helped. Thanks Kevin.
Anytime Dinesh!
Thanks for making the dfs codes so easy to grasp like all the other videos.
I enjoy your videos brother.
Let N,M be the number of nodes, edges in a general graph.
This problem can be solved in M+Nlog(N) time in a fashion similar to Dijkstra. Your algorithm runs in N(N+M) time.
In our case M=O(N) --> Nlog(N) vs N^2
Idea: undirected graph traversal
Create adjacency list
Perform DFS at every node
Until wall is reached
Save shortest path
Hey kevin, if u readin it, i very much liked the last condition in if in dfs
I got high on on how it takes care of walls.
room[i][j] < count will handle the condition for walls, as wall is equal to -1 that will always less than count;
Thanks for the awesome video 😊
How would bfs code change as compared to dfs?
Holes and caves
Trump Voter's favorite question
Hahah
What's the difference between adding to count parameter in dfs function call and incrementing count in the processing prior to that?
And why doesnt the solution return the board? Is this stated in the problem?
Just one question, can we use DP here? We can store the min distance from 0 and then increment by one. Pls tell.
This is really similar to the island questions
Thank you for the great explanation!
Such a great problem. Thanks for the video.
Hi - Thanks for the video. I'd appriciate if you could answer this question:
really nice explanation ! one suggestion is if you could use animations to explain the solution , that could really help us to understand in much better way .
1:57 is where the solution starts
why not use r and c when its matrix ? :) it will help us to understand . Thanks for your videos Kevin .
nice video. Really well explained.
This solution is exceeding timelimit! I wonder how i got submitted for you:)
We can solve it using multisource BFS in a very optimal way. Just add all the gates into the queue and keep on traversing level by level keeping the track of the visited cells. It can be solved in O(n*m) time complexity.
Dude thanks for teaching .. LC solution was complicated for me
Aravindh Saai Ravichandran anytime! Check out the interviewing service I made if you need help with understanding problems like this thedailybyte.dev/?ref=kevin I’d join a premium plan if you can!
Great explanation. Thanks
This has now become a leetcode premium question.😑
Could you explain why the time complexity is O(m*n) for this one? I understand that we are traversing through the entire grid which is m*n but do we not consider the recursive calls of dfs?
Worst case scenario, we have gate in bottom right cell and for each cell we run dfs which results in ( m*n) times for (m*n) cells, which is m2n2
What is the time complexity of this solution?
Update Time Limit Exceeded for this.
What's the runtime complexity? Seems we can traverse the grid N times where N is a gate
We're doing standard DFS for matrix representation of n*n. Thus seems time complexity is O(n*n)
O(number of 0s * number of cells)
@@goodwish1543 (number of rows * number of cols) + (number of 0s * number of rows * number of cols)
Will this solution overwrite other gates?
I am not sure how this would ignore Walls while traversing.
It doesn't, actually it just evaluate this cells as counts with big values, so the first condition rooms[i][j] < count skips this cells
TLE (23rd Nov 2021)
You are great man!!
You are awesome man!
Fantastic explanation!
dark vader thanks!
I can't understand the recursive part at 6:09 can someone pls explain?
I have been leetcoding for past 1 year , Is 1 more year of leetcoding enough to crack FANG internship?
hard to say because it depends on comfortable you are with these questions and topics. If you need help preparing for these interviews I'd suggest signing up for the interviewing service I created thedailybyte.dev/?ref=kevin I'd join the annual plan if you can!
Ur bgm pls😂😅
It's such a clean and easy to understand solution, but now it gives TLE (June 7th 2022).
Same.