SHORTEST PATH IN A BINARY MATRIX | LEETCODE 1091 | PYTHON BFS SOLUTION

[@jedholtman9075]

A corollary is that the range returned (assuming a path exists) is n

[@thedropshipper96]

in this solution how it is ensuring its the shortest path it just going random path and there is no conditions that tells its the shortest path. Can you please explain this?

[@crackfaang]

You can think of the matrix and the paths as an undirected, unweighted graph. The BFS algorithm is guaranteed to give the shortest path when traversing through such a graph. You can think of this intuitively as BFS will explore all paths of length N, before moving onto paths of length N + 1. Also we can sanity check this by the fact that the solution is accepted. The chances of us going down a “random” path and passing all test cases every time we submit is essentially impossible

[@pravinpoudel1307]

@@crackfaang this is a valid question, i think your solution works because you in your direction, you are putting diagonal direction at last

[@pravinpoudel1307]

@@crackfaang i am sorry i was wrong, it does matter because the distance is height of the tree or number of level you had to trace and whenever you get the answer, it mean that is the fastest !!! unlike in DFS, in BFS first one to meet the base condition is the shortest or fastest

[@Jessica-gu6rn]

Great video. If the output is to print out the shortest path with all nodes in it, how would you solve it? thanks!

[@suraj8092]

Shouldn't it be N*N time complexity?

[@avivsmadja9159]

How Can you do the same but mark the Path and not only return what length it is

[@rachnaramkumar]

Thanks for another great video :) Can you solve Leetcode 31. Next Permutation? I don't see many videos for it. I do see a couple of solutions posted in the discuss section, but I can't wrap my head around it. Thanks :)

[@crackfaang]

Haha sure. By the way I absolutely hate Next Permutation. It’s a question I can write a solution for but I have no idea how the proof that the solution is valid works 😂

[@rachnaramkumar]

@@crackfaang I get what you mean. I got the solution, but I don't exactly know why it's the solution :P

[@GeraudKAMENI]

time complexity is the size of matrix N*N

[@akhileshshahare]

Clear explanation. Thanks!

[@crackfaang]

Thanks for your support! Make sure you subscribe so you don’t miss future uploads

[@jeremypruitt237]

Great explanation! Thanks much!!

[@crackfaang]

Thanks for the kind words! Make sure to subscribe so you don’t miss future videos and let me know if there’s any problems you’d like me to solve

[@muskanmall4401]

thanks man!

[@ashleypowell8066]

Great explanation. Thanks! Definitely subscribing.

[@SaurabhSingh-vv7wt]

great job man , but can u provide the o(n) solution

[@crackfaang]

This is O(N) where N is the number of cells in the grid. I may have said O(rows * cols) but that's the same thing in the end. It's linear in that it depends on the size of the grid

[@sarayarmohammadi3376]

Thank you very much!

[@_7__716]

Thanks. Please zoom a bit for mobile users.

[@crackfaang]

Thanks for the feedback. Unfortunately almost all of my audience is desktop users and if I zoom in, then you won’t be able to see the full solution in code and will have to scrub the video to read it which I find is a very bad UX

[@crackfaang]

I am currently on vacation in the Bahamas but when I get back I will try to make a GitHub repo with all the solutions for you

[@romanivanov6183]

Didn't get why it was the shortest one?

[@crackfaang]

Breath First Search in an un-directed graph is always guaranteed to be the shortest path. There's probably a proof out there somewhere but this is just a general thing you learn and apply for these categories of problems.