Find the Safest Path in a Grid - Leetcode 2812 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/find-th...
0:00 - Read the problem
3:48 - Drawing Explanation
17:13 - Coding Explanation
leetcode 2812
#neetcode #leetcode #python

[@michael._.]

neetcode makes a hard question disguised in medium actually feel like a medium under 30 minutes

[@nathan_ca]

Thanks! now I watch you video to do mental exercise rather than wasting time on tiktok or yt shorts for nothing.

[@jegadheeswarank6290]

🙌

[@JamesBond-mq7pd]

I do the same. TikTok is wasting your life

[@nirmalgurjar8181]

According to me, this is top quality problem which involves multi source bfs, dfs, binary all in one solution.

[@meemee417]

spent like an hour solving this, half of which was wondering why this was considered a medium

[@SameerRehan-tt4lh]

Love the way you tackle a problem, I even want to think of approaches like you sir,

[@yang5843]

Thanks for making this video, there are multiple parts to this problem

[@abhimanyuambastha2595]

Solved this problem on my own using the approach from a similar problem 1631. Path with minimum effort. Used a modified dijkstra with max heap. Resulted in TLE but passed 1000/1036 testcases, so pretty happy with my solution. Came here for the neetcode special optimized solution and wasn't disappointed

[@black2342]

Thank you for finding the safest path in LeetCode problems.

[@business_central]

Man I did the two other problems you mentioned Walls and gates and swim in rising water, but gosh it didn't came to mind when I was doing today's problem, at least not within the 25 minutes I allow myself. Still long way to go. Thanks for all your efforts!

[@StellasAdi18]

Best explanation! Thanks for wonderful content.

[@kwakukusi4094]

thanks for the explanation, i could not have solved it without your explanation but once I understood the question I realised why it was a medium problem

[@mudit7394]

Only simple improvements like removing the dict improves the code massively: class Solution: def maximumSafenessFactor(self, grid: List[List[int]]) -> int: N = len(grid) directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] q = deque() def inside_bounds(r, c): return 0

[@NeetCodeIO]

Yeah as long as modifying the input is allowed this is a great solution, thanks for sharing this variation

[@anand_dudi]

Whenever any problem goes above my head i straight find neetcode video on youtube 😄

[@rahulsihara8946]

Jokes on Leetcode, i didnt event try to solve it. Just came here to understand the problem. :D

[@shahzodshafizod]

😂😂

[@jagrutitiwari2551]

I was searching for your video for this question in the morning. I thought you won't upload it today.

[@felipesan774]

Thanks bro, great video

[@shubhamchouksey9904]

thankyou neetcode

[@HuyLe-zx8ko]

good job bro 🤘

[@hasibulfor]

O my lord, in 1.5x I just saw a thriller movie!!! Keep it up bro...

[@soumyajitganguly2593]

@26:14 Dijkstra / using heap is not the most optimal. You can do this using a dequeue (0/1 BFS)

[@Ziviani]

I was "lucky" enough to get a version of this question in my interview. I tried solving it with Dijkstra setting the "unsafe" cells to infinite, so when calculating distances my algorithm would never consider that path. But my implementation sucked just like the feedback I had. 😀

[@ay5960]

I was reading the recent leak/whistleblower on reddit. Came out today about reverse engineering alien crafts. It was mentioned these crafts are not autonomous but use some object avoidant 3d Dijkstra algorithm and now I come here and see neetcode has a object avoidant Dijkstra question.

[@thejvenkat3534]

NeetCode If you don't mind can you also analyse the top solutions, because sometimes simple improvements to your solution will bring down the time a lot and can help us understand why it takes more time.

[@DBagg-zz4ip]

Oh man. I thought I had this one but timed out on the last test. Set all the 0 cells to 400 and BFSed from every thief, only adding a neighbor if its value was higher. Thought that would cut down on time complexity but now I visualize a case where thieves cockblock each other back into n^4. Didn't think of just putting them in one deque.

[@priyanshagarwal8490]

Can you explain 166. Fraction to Recurring Decimal next Pls..

[@AbhishekSingh-xq4cu]

How to see locked problems of leetcode, how did you open walls and gates in neetcode?

[@ritikaagrawal769]

had to take hint and apply binary search and finally solved it on my owm in 1.5 hrs. But watched your and realised it could be done a bit easily. Complex problems teach you stuff, you did not want to learn. XD

[@pastori2672]

starting to take leetcode less and less seriously tbh it doesnt feel like its making me any better but i think im just coping

[@pastori2672]

i actually believe i did the first part but just ran another regular bfs instead of modified dijkstra's and got tle..

[@Antinormanisto]

I want to cry, i tried to solve this for 4 hours(

[@rohitkumaram]

Just a suggestion, don't try more than 20-30 minutes look at the solution , build your knowledge base by looking at the solution, and then put that question with link into an excel sheet to solve after 1 month. Still can't solve it , look at the solution understand it then put in the list to solve in next month. repeat until you can tackle it easily. For example this problem is going in my JUNE month list. Try this very effective.

[@YoungLeaf79]

You haven't solved it but probably learned a ton so still it's a win imo.

[@EduarteBDO]

I solved it in 5, Idk what I'm doing with my life.

[@saumypandey2288]

​​@@EduarteBDO5 what?? Hrs, minutes ,secs

[@EduarteBDO]

@@saumypandey2288 hours.

[@BilalShaikh-tn9wu]

I'll just let the thieves rob me if it means coming up with this on my own

[@jayliu5021]

Great work! But, I have a question that why sometimes we use Dijkstra BFS to search our neighbor we can't set the visited[neihbor] to true;, but here we can set the visited[neighbor] to true? I just pop from the queue and set visited to true once and BFS search not set the visited[neighbor] to true, and it is also work (but may time limit exceed).

[@rocmewtwo]

Hello neetcode, I found you have two types of dijkstra algorithms. some time you add if condition after heap pop, and that is code template in course you teach. w1, n1 = heappop(heap) if n1 in visit: continue visit.add(n1) But some time you write like as video, make me a little confused.

[@MohanRam-mq2pk]

tell me how your accent is so good?

[@soumyajitganguly2593]

The free version of Walls and gates is Rotten oranges

[@ben94_]

me: i should really start trying more mediums... the mediums:

[@anti-tankartur677]

I tried the bruteforce solution the first time i got this problem. I solved half the test cases and tle on the other half. Feels like shit.

[@cheezdog1343]

Can someone please explain to me why after we create the safeness grid using our first BFS, we can't use DP on the grid starting from the bottom right corner to calculate the solution in O(n^2) time? I tried implementing this solution but I'm getting 7 test cases failed, and I don't know if its due to my error or the fact that my approach doesn't work

[@cheezdog1343]

Update: I think at least that DP cannot be used since you can move in all four direction, not just left or right to create a path, so this would make DP solution very hard to implement since you would have to store additional info to make sure you don''t revisit square. Or smthg like that. Who knows. Fuck this.

[@EduarteBDO]

@@cheezdog1343 I think I did that, I used a new grid to store the values but got tripped by edge cases until I started traveling in 4 directions instead of just right/down

[@mementomori8856]

127 lines in Go lol. I miss Java, it had every data structure under the sun.

[@bhaskarpilania]

"leetcode laddoo" 🤣

[@advaitbajaj4241]

Did you say ladoo? 😂😂

[@finfan2101]

when?

[@ronbuchanan5432]

You're wrong about the distance metric. The shortest path depends on the metric. Manhattan distance (Taxicab distance) means you can only travel on a grid, like cabs in Manhattan. Chebyshev distance is similar but you can travel diagonally as well, like the King piece in chess. So saying "Manhattan distance is the shortest path" is just wrong and it's important to know that. Anyway thanks for the explanation!

[@NeetCodeIO]

Is it wrong in the context of this problem where we can only move in 4 directions though?

[@ronbuchanan5432]

@@NeetCodeIO okay you're right they have stated above what an "adjacent cell" is, so it a needless complication but at the same I see it as opportunity to educate people.

[@staywithmeforever]

Just to suffer

[@user-pv4xn3sg7j]

Awwwsome video man

[@JamesBond-mq7pd]

Still didn't understand. So hard

[@shynalprasad5508]

Bruh did you said ladoo?

[@akash-kumar737]

These type of question is pure cheating and I am not playing this game.

[@MrWuggles]

aint no way this is a medium lol

[@juanmacias5922]

Yeah, this being a "medium" is suss AF...

[@susdoge3767]

i'd just leave this shit

[@akshayiithyd]

I solved it using the hints Leetcode provided, but it gives me a TLE

[@akshayiithyd]

Okay nevermind, should have done a multisource BFS

[@aanurraj]