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
man a year ago i couldnt solve something like this, now it seems easy when u know the patterns. I was surprised that this problem didn't take me longer than 30min to solve on first attempt!
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!
Thankyou for specifiying the real difficulty of the problem where needed! Just when my confidence level is about to drop, you say “this one is pretty tricky” and I am like phew😅
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
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. 😀
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.
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.
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.
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.
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).
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.
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
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 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.
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
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.
@@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
neetcode makes a hard question disguised in medium actually feel like a medium under 30 minutes
Thanks! now I watch you video to do mental exercise rather than wasting time on tiktok or yt shorts for nothing.
🙌
I do the same. TikTok is wasting your life
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
Yeah as long as modifying the input is allowed this is a great solution, thanks for sharing this variation
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
According to me, this is top quality problem which involves multi source bfs, dfs, binary all in one solution.
man a year ago i couldnt solve something like this, now it seems easy when u know the patterns. I was surprised that this problem didn't take me longer than 30min to solve on first attempt!
Thanks for making this video, there are multiple parts to this problem
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!
Thankyou for specifiying the real difficulty of the problem where needed! Just when my confidence level is about to drop, you say “this one is pretty tricky” and I am like phew😅
Love the way you tackle a problem, I even want to think of approaches like you sir,
Thank you for finding the safest path in LeetCode problems.
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
spent like an hour solving this, half of which was wondering why this was considered a medium
@26:14 Dijkstra / using heap is not the most optimal. You can do this using a dequeue (0/1 BFS)
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. 😀
Whenever any problem goes above my head i straight find neetcode video on youtube 😄
Best explanation! Thanks for wonderful content.
O my lord, in 1.5x I just saw a thriller movie!!! Keep it up bro...
Jokes on Leetcode, i didnt event try to solve it. Just came here to understand the problem. :D
😂😂
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.
I was searching for your video for this question in the morning. I thought you won't upload it today.
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.
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.
thankyou neetcode
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.
Thanks bro, great video
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).
hallelujah GodFather hallelujah love you content and your way of expression
Can you explain 166. Fraction to Recurring Decimal next Pls..
I want to cry, i tried to solve this for 4 hours(
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.
You haven't solved it but probably learned a ton so still it's a win imo.
I solved it in 5, Idk what I'm doing with my life.
@@EduarteBDO5 what??
Hrs, minutes ,secs
@@saumypandey2288 hours.
i actually believe i did the first part but just ran another regular bfs instead of modified dijkstra's and got tle..
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
How to see locked problems of leetcode, how did you open walls and gates in neetcode?
starting to take leetcode less and less seriously tbh it doesnt feel like its making me any better but i think im just coping
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.
wow!
good job bro 🤘
The free version of Walls and gates is Rotten oranges
I'll just let the thieves rob me if it means coming up with this on my own
tell me how your accent is so good?
127 lines in Go lol. I miss Java, it had every data structure under the sun.
me: i should really start trying more mediums...
the mediums:
if NeetCode takes 30 min to explain how would I solve this in an assessment of 45 min? this is insane
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!
Is it wrong in the context of this problem where we can only move in 4 directions though?
@@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.
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
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.
@@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
Did you say ladoo? 😂😂
when?
"leetcode laddoo" 🤣
bro was pissed looool, i hear it
Still didn't understand. So hard
These type of question is pure cheating and I am not playing this game.
Bruh did you said ladoo?
Just to suffer
I solved it using the hints Leetcode provided, but it gives me a TLE
Okay nevermind, should have done a multisource BFS
Yeah, this being a "medium" is suss AF...
aint no way this is a medium lol
i'd just leave this shit
fake account and you seem to be using the same voice?
No it's still me
Awwwsome video man