Walls and Gates 

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?

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.

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

Nice!!!

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

Anytime and will do!

Anytime, I hope it was helpful!

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.

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; )

room[i][j] < count will handle the condition for walls, as wall is equal to -1 that will always less than count;

Anytime Dinesh!

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

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'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)

dark vader thanks!

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!

Hahah

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

Same.