Shortest Path in a Binary Matrix - Leetcode 1091 - Python

[@NeetCodeIO]

If you're looking for today's daily LC problem, I already have a video for it here: kzbin.info/www/bejne/hYfKgXSAft6LbNE

[@def__init]

Dude got a job at google just to learn their YT algorithm so now he’s uploading daily, respect 🤝😂 Quality has been great lately keep it up

[@john_youtube]

your videos have helped me land multiple offers at large and small companies. your efforts in sharing this knowledge freely has played a part in transforming my life from a finanically struggling student and barista to a senior software dev at one of the big 5. you're making a huge impact in people's lives and i hope you keep sharing your talents with the world.

[@venkatasundararaman]

Small optimization. You can do a boundary check before adding it to the queue. This way we can prevent unnecessary push and pops from the queue and it will improve the memory complexity as the visit set will not store the out of bounds positions.

[@Midlifecrypto]

This a good problem for anyone trying to learn shortest path/BFS problems

[@bahadrbasaran8908]

Good stuff! I think there is one mistake in the space complexity analysis at 4:35 tho. Even in the worst case (a grid full of 0s), the queue size will never expand to O(n^2). You can try it by printing the queue in each iteration. For a grid with dimensions m x n, the worst case space complexity would be O(min(m, n)).

[@pauljones9150]

Good stuff as always. For some reason wasn't showing up on my feed until 11:50, but must have been a bug. All the best for the work you do

[@kirillzlobin7135]

Would it be a good idea if in the very beggining of the function we will consider this edge case: if (grid[0][0] === -1) return -1

[@Goebschae]

my solution in the end was not nearly as efficient and i had a list of visited nodes too. unfortunately with this i failed the time constraint at some 100x100 matrix but one thing that in the end got me through the time constraint was deleting the visited nodes list and replacing it by grid[x][y] = 1. since i regularly had to check whether grid[x][y] == 0 anyway setting it to 1 basically marked it as visited

[@MP-ny3ep]

Thank you for the daily leetcode problem

[@zeta_meow_meow]

Thank You for the Upload !!

[@sarahzaki03]

Thank you

[@nkeng1]

Hi Neet, quick question - what if there are multiple paths to the end? how does the implementation guarantee that the first time it returns, that is the shortest path? is this because were adding to the queue level by level?

[@lazyemperor5182]

Since this is BFS, we u find the target node in the queue it is guaranteed it is shortest path

[@podilichaitanyaakhilkumar4911]

Please upload hard leetcode problems as many as possible.

[@subee128]

Thanks

[@corrogist692]

just a small detail, can we modify the grid in place so that we dont need to keep track of the visited

[@netanelkomm5636]

Did the exact same in C, and im getting TLE. The thing is, I get TLE only when submitting, but when adding the test case it TLE'd on, I pass it using run. THANKFULLY - I was able to solve it by converting the visited array into a hashmap of size 100 * 100, so I don't have to traverse it in o(n), and can just access the element i need at o(1). Pay attention to the constraints! They are sometimes helpful, especially in statically typed languages like C.

[@user-wk4uq5bi4n]

can you share the change you made. I am getting the same error

[@ronaldmcsidy763]

Can someone explain how is this the shortest path? We did not calculate minimum length anywhere. Sorry but I am a noob I feel like

[@vuanhkhoa9715]

BFS guaranteed to find the shortest path if one exitsts. He also tried to emphasize that by drawing the layers at 4:08

[@davidoh0905]

At this point, is DFS better? maintaining `visited` is a lot more intuitive that way

[@AmolGautam]

Thank you.

[@tarunthomaseapen5415]

Is the code available in the site or github? I’m specifically looking for a java implementation if present.

[@ssy13542]

We can flip the visited cell to 1 so that we don't need to check if the cell is visited or not

[@lazyemperor5182]

I have a question can't we use recursion like the problem of rat in a maze

[@colefrankenhoff1428]

I tried that. It gets messy, because it's much harder to keep track of which nodes have been visited, but you can get it to work. But bfs in this way is a very powerful algorithm to learn, and iterative solutions are just generally better than recursive ones

[@sanketduhoon235]

Hi, can someone help me out with my mistake, I did it without passing length in queue instead I calculated it separately, but I am getting answer+1 as my result in few cases class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: if grid[0][0]==1: return -1 N = len(grid) visit =set() q = deque() q.append((0,0)) visit.add((0,0)) res=1 dir = [[1,1],[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[1,-1],[-1,1]] while q: r,c = q.popleft() print(r,c) if r==N-1 and c==N-1: return res for dr, dc in dir: dr+=r dc+=c if dr in range(N) and dc in range(N) and (dr,dc) not in visit and grid[dr][dc]==0: q.append((dr,dc)) visit.add((dr,dc)) res+=1 return -1

[@tirthdoshi1337]

When you pop the value why not change the value at that row and column to 1 so that we know that the value is visited. No need to keep the visited set at all.

[@joelgantony]

Why isn't DFS not possible in this case?

[@Benstokes555]

WONDERFUL EXPLANATION. just a small sugesstion to whoever is not understanding stuff here :- it means either youre not well versed with the basics(u need to practice more problems before coming here) or u need to try thr problem on leetcode before directly diving into the solution.' HOPE THIS HELPS :0

[@harunguven8581]

Older leetcode theme was better, I still use that.

[@adityakulkarni5577]

Normally a fan of your videos but this one missed the mark tbh. Please dont write stuff then come back to it saying "oh actually lets delete this". Makes understanding stuff pretty difficult. Thank you for everything though.

[@Ahmad-h3z1v]

I think the video was spot on tbh? What made u get tripped up?

[@prateekmohanty8315]

I dont understand why DFS wont work here , I have done DFS and getting a wrong result why is that class Solution { public: long long solve(vector&grid,int i,int j,vector&vis) { // base case int n=grid.size(); int m=grid[0].size(); // base case if(i=n)return INT_MAX; if(j=m)return INT_MAX; if(grid[i][j]==1)return INT_MAX; if(i==n-1 && j==m-1)return 0; long long moveUp=INT_MAX; long long moveDown=INT_MAX; long long moveLeft=INT_MAX; long long moveRight=INT_MAX; long long moveDiag1=INT_MAX; long long moveDiag2=INT_MAX; long long moveDiag3=INT_MAX; long long moveDiag4=INT_MAX; // move up if(i-1>=0 && vis[i-1][j]==0) { vis[i-1][j]=1; moveUp=1+solve(grid,i-1,j,vis); } // move down if(i+1=0 && vis[i][j-1]==0) { vis[i][j-1]=1; moveLeft=1+solve(grid,i,j-1,vis); } // move right if(j+1=0 && j-1>=0 && vis[i-1][j-1]==0) { vis[i-1][j-1]=1; moveDiag1=1+solve(grid,i-1,j-1,vis); } // move diag-2 if(i-1>=0 && j+1