Walls and Gates - Multi-Source BFS - Leetcode 286 - Python
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Problem Link: neetcode.io/problems/islands-...
0:00 - Read the problem
1:40 - Drawing Explanation
7:00 - Coding Explanation
leetcode 286
#bfs #python - Věda a technologie
This is a Premium LC Problem but you can solve it for FREE here: www.lintcode.com/problem/663/
thanks a lot man 👍👍 i will try it out here ☺️
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 :).
easily goated
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.
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"
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
I like how neat your code is with all your helper functions. So easy to understand, thanks Neetcode!
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
Great Explanation, this problem is similar to Rotten Oranges one right.
Yes! That was a tricky one as well.
as well as 0-1 Matrix
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.
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 :)
6 mins into the video and solved the problem. This guy doesnt waste time :)
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.
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)
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.
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
thank you for the clean explanation and codes.
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.
It is very clear!! Thank you!!!!
great explanation!
@NeetCode, how do you pick which question to go over?
I don't understand one thing, will the initial ordering of the gate index pairs in the queue affect the final result?
Amazing video
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.
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.
I agree with this. And it is a bad practice to use list/queue like this. I would recommend double queues/lists.
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.
Sorry if it's a silly question, but how can your code work if youre not returning anything at the end of the function?
It's mentioned in the problem statement that we have to only modify the grid. So we don't need to return anything.
simultaneous BFS, sounds cool
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.
Today, I tried the exact code you've written here and it shows "Time Limit Exceeded".
you might have missed any edge cases
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));
}
}
@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.
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
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
Wow I love this problem.
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.
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.
My boiiii neet code
Can you explain how the time complexity of DFS Solution is O((mn)^2)
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)
@@sapnavats9105 Thanks :)
At @1:56, I guess he meant wall not gste.
Thanks!
Thank you so much!!!
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
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.
I solved this with brute force bfs in java but multiple source is new to me so thank you! :)
You made it seem easier
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?
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.
could you also solve this with dynamic programming
Why doesn't normal BFS work in this scenario?
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 🤠
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!
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]
Hi can u do k inverse pairs
Heyyy what about DFS from the gates only.
I think in that we can retain the time complexity.... Correct me if I'm wrong
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.
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
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.
@@NeetCode K inverse pairs please :(
same as rotting oranges
Just a heads up, the code in your video is correct, but the one in your website is wrong
Thanks for letting me know, which site did you try running on?
No need for visit set, just check if tile is not visited by its value
1:54 you mean a wall, not gate.
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.
How many times can you visit each cell? It's a constant value I think
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).
Regardless how many gates you have, each room at most be visited once. So indeed time complexity is O(mn)
@@chenhaibin2010 One room may be visited from different gates because the distances are different.
@@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
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]
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