Walls and Gates - Multi-Source BFS - Leetcode 286 - Python

[@NeetCode]

This is a Premium LC Problem but you can solve it for FREE here: www.lintcode.com/problem/663/

[@aayushchhabra9805]

thanks a lot man 👍👍 i will try it out here ☺️

[@dk20can86]

Only sad thing about lintcode is that it doesnt include the datastructures-js queue and priority-queue packages for TS/JS :(. Good opportunity to practice implementing these data structures yourself though i suppose :).

[@isaacaholic]

easily goated

[@kevinwang7811]

Great explanation! Just one note: technically we don't need a visit set, because if a cell value is not INF, it means the cell is one of: {gate, wall, a cell with the shortest distance updated already}, we won't visit the cell again.

[@Anonymous_moron]

You're right! I refactored his solution, and instead, just checked if the (row+x, col+y) was between 0, 4 (0 and row/column max). Using the visited set adds O(m*n) time complexity, and O(m*n) space complexity, so there is no penalty for using it. I'm going to guess that he included it because the fact that they give you a designator for unvisited rooms is a rare luxury, and it may be counter-productive to take away "I don't need to keep track of what I visited when using BFS"

[@HansSung]

rows, cols = len(rooms), len(rooms[0]) q = collections.deque() # 1. traverse matrix, get all the gate into queue for r in range(rows): for c in range(cols): if rooms[r][c] == 0: q.append((r, c)) # can? yes! # 2. start BFS, update INF step = 0 while q: step += 1 for i in range(len(q)): r, c = q.popleft() for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]: row, col = r + dr, c + dc if (row in range(rows) and col in range(cols) and rooms[row][col] == 2147483647): q.append((row, col)) rooms[row][col] = step

[@RandomShowerThoughts]

don't we? We're running bfs from different points

[@codename4795]

​@@RandomShowerThoughts But from each gate, you reach a particular depth concurrently - meaning the same depths will be seen by both the gates (because in bfs the breadth is explored first). Hence the one that reaches a particular cell first would be the closest!

[@echochen889]

2 suggestions: 1) no need for a visited set since we can just check if value is INF(meaning unvisited) 2) no need to control the layer, since every dist=2 cells will be enqueued after the dist=1 cell and rooms[nexti][nextj] can be set as rooms[i][j]+1. Hope this makes sense

[@pinkpig7505]

Can you explain the second point??

[@AlejandroRuiz-pd6ci]

I like how neat your code is with all your helper functions. So easy to understand, thanks Neetcode!

[@mostinho7]

Done thanks, this is same logic as the shortest bridge to connect 2 islands problem, you start a bfs from multiple start positions (in the case of islands you start bfs from all the nodes in the first island, but in this case we start bfs from all the gates (even though the gates aren’t connected, that’s fine) Our queue is initialized with the gates and then we snapshot the queue size and do bfs (keeping a distance variable that you increment everytime you complete a layer)

[@ammarqureshi2155]

great work neet! i would suggest you keep doing these problems that require subscriptions because a lot of the good problems are subscription based on leetcode. Again, keep up the good work man :)

[@amitupadhyay6511]

6 mins into the video and solved the problem. This guy doesnt waste time :)

[@avinash-xh6qw]

Great Explanation, this problem is similar to Rotten Oranges one right.

[@shrimpo6416]

Yes! That was a tricky one as well.

[@hillarioushollywood4267]

as well as 0-1 Matrix

[@Kai-iq2ps]

Neat. Thanks a lot. You can also save some extra space by not using "visited" set. Instead you can just check whether rooms[r][c] != 2**31 - 1. Of course, this requires some change in code structures.

[@Comusus]

Do not need to maintain a visited set or distance var since (1) we can determine if a cell has been visited if it's val is not INF and (2) gate value is 0 so we can increment by 1 for neighboring cells.

[@ameynaik2743]

Can you please solve 787. Cheapest Flights Within K Stops? This is a very tricky one, the DIJKSHTRA's TLE on this but a modified BFS works. Would be great to see how you solve it.

[@scienceofart9121]

When you say subscribe it just glows, its pretty good actually. Thanks for the solution btw very clear explanations

[@thePontiacBandit]

Brilliant. The intuition here is simple but absolutely brilliant. I don't think I would get the optimal solution for this one without watching this video.

[@niravarora9887]

I like creating a helper function for BFS rather than defining an array for the direction and looping through it and making the code look very messy, also this aligns better with DFS as we keep recurse with neighbors there by passing similar parameters.

[@latenspace]

in my solution i have done `grid[r][c] = min(dist + 1, grid[r][c])` during neighbors traversal. but just by sequentially adding the gates to the queue we still endup with the min distances for each cell anyway. i figured the next/last assignment `grid[r][c] = dist` will override the old distance and that ultimately is the min distance, that's not something that's trivial at first. nice work

[@louisuchihatm2556]

I've been scratching my head though why the cells are getting overridden after every loop.

[@SaahasBuricha]

great video, how do you know when to use bfs and when to use dfs for these graph problems?

[@harishsn4866]

Today, I tried the exact code you've written here and it shows "Time Limit Exceeded".

[@hillarioushollywood4267]

you might have missed any edge cases

[@shrimpo6416]

I am not sure but I think it should be len_q = len(q) then for-loop, instead of using len(q) directly because the length of q would change in for-loop.

[@JW-bx4su]

I agree with this. And it is a bad practice to use list/queue like this. I would recommend double queues/lists.

[@AnthonyInSanDiego]

technically, len(q) will be called once at the very beginning of the for loop. so the range driver from len(q) will not change during the for loop execution.

[@hhcdghjjgsdrt235]

simultaneous BFS, sounds cool

[@rahul911017]

I found adding the neighbors to the visited set even before we processed them a bit confusing. Modified the code a bit to make it clearer that we visit a node only when we update the distance. class Pair { int row; int col; Pair(int r, int c) { row = r; col = c; } } class Solution { int rows; int cols; Queue q; boolean[][] visited; public void wallsAndGates(int[][] rooms) { // base case if (rooms == null || rooms.length == 0) { return; } rows = rooms.length; cols = rooms[0].length; q = new LinkedList(); visited = new boolean[rows][cols]; // initialize the visited matrix for (boolean[] brow : visited) { Arrays.fill(brow, false); } // lets add all the gates to the queue first for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (rooms[i][j] == 0) { Pair cell = new Pair(i,j); q.add(cell); } } } // lets do a BFS starting from all the gates and mark the distances // of all the neighboring cells int dist = 0; while (!q.isEmpty()) { int qlen = q.size(); for (int i = 0; i < qlen; i++) { Pair cell = q.poll(); // mark the distance for this cell from the gate int r = cell.row; int c = cell.col; if (visited[r][c] == true) { continue; } rooms[r][c] = dist; // mark this node as visited visited[r][c] = true; // add all the valid neighbors to the queue for the next stage addNeighbors(rooms, r + 1, c); addNeighbors(rooms, r - 1, c); addNeighbors(rooms, r, c - 1); addNeighbors(rooms, r, c + 1); } // we have processed all cells from this level // so increment the distance for the next level dist += 1; } } // method to add the valid neighbors to the queue private void addNeighbors(int[][] rooms, int r, int c) { // do a bounds check if (r < 0 || r >= rows) return; if (c < 0 || c >= cols) return; // skip if it is a wall or if it has already been computed if (rooms[r][c] == -1 || visited[r][c] == true) return; // this is an uncomputed cell q.add(new Pair(r,c)); } }

[@AbhijithVMohan]

Multi source BFS here can be reduced to plain old BFS with single source, if we imagine a dummy node that has 0 cost edges to all the source nodes.

[@kadiryasar2225]

Thanks for solution, is the for loop at line 22 really required ? because, it's a queue, all new positions will be appended to the end.

[@eile4219]

Not require, but you will needs to write the code differently to keep track of the current dist. Also, the visited set is not required. Just check if the room has value that's less than or equal to the current dist.

[@AdrienAranda]

Sorry if it's a silly question, but how can your code work if youre not returning anything at the end of the function?

[@subhadeepmandal9891]

It's mentioned in the problem statement that we have to only modify the grid. So we don't need to return anything.

[@thepardhu100]

At @1:56, I guess he meant wall not gste.

[@chenhaibin2010]

thank you for the clean explanation and codes.

[@rishabsharma5307]

Can you explain how the time complexity of DFS Solution is O((mn)^2)

[@sapnavats9105]

according to my understanding, the max depth of a dfs functions can me equal to the size of the grid which is equal to the m*n and in the worst case we might have to call this dfs function for all the elements present in the grid which is again equal to m*n making the overall time comprexity equal to O((mn)^2)

[@rishabsharma5307]

@@sapnavats9105 Thanks :)

[@hillarioushollywood4267]

@NeetCode, if the initial gate has been added into the queue, all the empty neighbor rooms will get added into the queue and marked them visited then when will the second gate get a chance to update the distance of the empty room? To handle this, in the video @4:50 you said that we will do BFS on both the gates at the same time but it doesn't look that way from the code as we are only iterating the rooms matrix iteratively.

[@Yuipser]

the line "for i in range(len(q)" let us only work on the rooms in the same layer so for the first len(q) popleft()s, we are adding room next to ALL the initial gates, the rooms are added to the end of the queue when we finish the first len(q) popleft()s, we then iterate on the next layer, another round of popleft() for len(q) times (here the len(q) is updated to the num of rooms we added previously). so, the rooms are handled layer by layer and this is BFS

[@beeramrahulreddy11]

Actually we can make an arbitary node and connect it to all potential sources and just run a normal BFS and at the time of finding out ans just deduct minus 1 from it

[@stanislawakutyepov7297]

great explanation!

[@MrKB_SSJ2]

I don't understand one thing, will the initial ordering of the gate index pairs in the queue affect the final result?

[@shklbor]

there's a difference in how you solved problems 3 years ago and 2 years ago. you got fairly smart later that year after you joined google 🤠

[@kirtipalve1772]

Thank you for the wonderful explanation! I wanted to ask, why are we maintaining a visit matrix? Why can't we just assume that if a cell == INF then it's not visited?

[@tejaskalpathi]

you actually can! a visited set is not necessary in this case but it may be due to the fact that sets have faster lookup times.

[@aaron7c]

Wow I love this problem.

[@kirillzlobin7135]

Amazing video

[@cici4148]

It is very clear!! Thank you!!!!

[@LaxGoatGaming]

Why doesn't normal BFS work in this scenario?

[@venkataraman7962]

You made it seem easier

[@jkim5118]

@NeetCode, how do you pick which question to go over?

[@hwang1607]

could you also solve this with dynamic programming

[@sofakingwetalldid2017]

Thanks!

[@NeetCode]

Thank you so much!!!

[@maxdegreat566]

My boiiii neet code

[@GingeBreadBoy]

Here's my version without a visited set. So O(1) space? Since queue only holds values temporarily? from typing import ( List, ) """ -1 = wall 0 = gate 2147483647 = empty room Time; O(N*M) Space: O(1) 1) Starting at every gate we will try to reach all possible values 2) Since we might revisit values, we will only continue if the current distance is greater than the new distance. This will also account for other gates, which might've been closer. 3) walls are considered impassable invalid positions! """ from collections import deque class Solution: """ @param rooms: m x n 2D grid @return: nothing """ def walls_and_gates(self, rooms: List[List[int]]): directions = [(0,1),(1,0),(-1,0),(0,-1)] ROWS, COLS = len(rooms), len(rooms[0]) que = deque([]) #Find all Gates for r in range(ROWS): for c in range(COLS): if rooms[r][c] == 0 : que.append((r,c, 0)) while que: r, c, distance = que.popleft() for d in directions: nr, nc = d[0] + r, d[1] + c if 0

[@allaboutthementality1594]

I solved this with brute force bfs in java but multiple source is new to me so thank you! :)

[@xiaoyatang22]

Save me from my alg assignment!

[@ttttully]

Hey, love your videos! Huge props to you. I wanted to request not to put the solution category in the title. I like to hear the problem description and think about the solution before knowing exactly what I will need to do to solve it. Thanks!

[@aayushchhabra9805]

hello i have a request i always follow your channel ...your solutions are awesome but these days u have made videos for problems that require subscription it is my req if u can make videos for those questions which are open and also if u can make a video on k inverse pairs

[@NeetCode]

Good point, I'll try to do mostly free problems. Also if you want to try this problem without Premium you can using the pinned comment.

[@algorithmo134]

@@NeetCode K inverse pairs please :(

[@dr4gonbloodx]

Just a heads up, the code in your video is correct, but the one in your website is wrong

[@NeetCode]

Thanks for letting me know, which site did you try running on?

[@hamoodhabibi7026]

Just wondering why do you add the coordinates as an array [r,c] in queue and as a tuple (r,c) in the visited set

[@NeetCode]

If I recall, you cant add arrays to a set in python, you have to use tuples. But I guess I could have also used tuples when adding to the queue for consistency.

[@BishalECE-uy5rn]

Heyyy what about DFS from the gates only. I think in that we can retain the time complexity.... Correct me if I'm wrong

[@danny65769]

I tried DFS from gates only and got time limit exceeded. Time complexity will be more than BFS (no longer linear), because you need to visit some cells more than once in order to update the distances if we found a shorter path to those cells from a gate.

[@jaimew4818]

class Solution { public void wallsAndGates(int[][] grid) { for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == 0) { traverse(grid, i, j, 0); } } } } void traverse(int[][] A, int i, int j, int n) { if(i < 0 || j < 0 || i >= A.length || j >= A[0].length || A[i][j] == -1 || n != 0 && A[i][j]

[@pranavsharma7479]

same as rotting oranges

[@zr60]

Your time complexity of DFS is wrong. You can visited the same grid multiple times in a DFS. Each dfs is 4^nm. So, the total time complexity is (nm)*4^nm.

[@NeetCode]

How many times can you visit each cell? It's a constant value I think

[@princezuko7073]

1:54 you mean a wall, not gate.

[@algorithmo134]

Hi can u do k inverse pairs

[@JW-bx4su]

Time complexity is not O(mn) because for each gate the bfs is O(mn), so if you have many gates, the final time complexity is O(m^2n^2).

[@chenhaibin2010]

Regardless how many gates you have, each room at most be visited once. So indeed time complexity is O(mn)

[@JW-bx4su]

@@chenhaibin2010 One room may be visited from different gates because the distances are different.

[@chenhaibin2010]

@@JW-bx4su the reason to introduce set visit is to keep track of which room has visited. the line 8 & 9 ensures the room will not be visited the 2nd time. So it guarantees every room can only be reached by one of the gates with minimum distance

[@colin398]

No need for visit set, just check if tile is not visited by its value

[@tinymurky7329]

My solution without visit from collections import deque class Solution: """ @param rooms: m x n 2D grid @return: nothing """ def walls_and_gates(self, rooms: List[List[int]]): # write your code here direct = [(0,1), (0,-1), (1,0), (-1,0)] q = deque() ROWS, COLS = len(rooms), len(rooms[0]) for r in range(ROWS): for c in range(COLS): if rooms[r][c] == 0: q.append((r,c)) while q: r, c = q.popleft() path = rooms[r][c] for dr, dc in direct: rr = r + dr cc = c + dc if (rr < 0 or cc < 0 or rr >= ROWS or cc >= COLS or rooms[rr][cc]

[@dontignore5567]

Your website has few bugs, hire me so that I can have a job, an opportunity to work with DSA God himself, and you get your website fixed.

[@habeebah6135]

I feel like failure 🥲. I cannot pass an OA. Maybe one day I will come back here to this comment and have passed an OA and gotten a full time job.