Shortest Path in a Binary Matrix - Leetcode 1091 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
4:40 - Coding Explanation

leetcode 1091

#neetcode #leetcode #python

[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

[bahadrbasaran]

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

[kirillzlobin]

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

[pauljones]

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

[MP-nyep]

Thank you for the daily leetcode problem

[podilichaitanyaakhilkumar]

Please upload hard leetcode problems as many as possible.

[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

[netanelkomm]

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.

[corrogist]

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

[nkeng]

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?

[ronaldmcsidy]

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

[ssy]

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

[davidoh]

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

[tarunthomaseapen]

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

[tirthdoshi]

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?

[lazyemperor]

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