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.
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
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.
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.
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.
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.
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; )
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
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?
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?
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!
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.
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!
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 .