Path with Minimum Effort - Leetcode 1631 - Python

[@criconicsbyme6713]

thanks neetcode, the question candy was asked in my interview...I saw ur video 😅 before the interview❤❤❤

[@LOVE-kf9xi]

cleared the interview ? did you get the job?

[@NeetCodeIO]

Damn thats good timing!!!

[@neo3000]

Lol may be the interviewer is watching this channel like me.

[@bundiderp5109]

You explain the thought process so understandably and in great detail that I don't even feel dumb anymore.

[@artinmayur]

While writing the code and explaining to us, can you pretend that you don't know the exact next line and try then try to solve.... There should be more iteration or going back to previous lines to add something new that we just realised while writing the code, like that..😅

[@kirillzlobin7135]

How come you could solve it in such a brilliant way. My first idea was to somehow use DFS. I wanted to go trough all possible routes and calculate the diff for them. And than return the min value. I wanted to do it with O (N ^ Infinity) time complexity, but this...... This is sooooooooo amazing....

[@damirsharip604]

thank you very much, this daily tasks are going harder and harder, needs new type of algorithms for me, union find, difikstra. I am glad to have you and you brilliant solutions with explanations. thank you

[@YT.Nikolay]

I solved this question myself, but I overcomplicated it, I built an adj list and traversed nodes using dijkstra's algorithm, but anyway, I proud I solved it myself, and huge part of this is you neetcode, thanks!

[@harmaina6060]

try to add these code and notes link in the discription please, would be very helpful

[@prajjwaldubey5787]

understood in one go excellent explaination, could you please solve leetcode 827 making large islands

[@Raymond-Wu]

instead of checking if the new row and new col is < 0 or == len(row)/len(row[0]) like you did in lines 20/21 you can just check if next_row in range(len(heights)) and next_col in range(len(heights[0])). Less text!

[@user-yj2ju9up8o]

it's less efficient

[@Raymond-Wu]

@@user-yj2ju9up8o Is it? What's your thoughts behind that?

[@dankiy3679]

Could you please help me understand why we should use Djikstra algorithm here? I understand that we can use it here but how much faster will it be compared to the regular DFS with memoization storing the cost to reach (row - 1, col - 1) element?

[@royd-l]

I believe the big O is the same for Djikstra and DFS but Djikstra has a faster runtime complexity on average because its traversal is more directed than DFS, meaning it is technically more optimal

[@faridahmed6252]

I hope we all recognise that this is too genius of a solution

[@gradientO]

so bfs with a priority Q instead of normal Q?

[@kamilrudny1884]

More like dijkstra's algorithm rather than bfs

[@alissabrave424]

how this comes to find min path we are trying to find max in every time?

[@schan263]

Great video but I think the original and "corrected" time complexity is wrong. Can you explain how you came up with the "corrected" time complexity if you think it is correct?

[@nosh3019]

very. clear, thanks!

[@StellasAdi18]

Thanks for amazing explanation. Do we need to check visit condition on line 22 as it’s checked on line 12 when popping?

[@truongquochung4858]

It's not required, but doing so will avoid unnecessary heap push -> reduce the time complexity significantly

[@pastori2672]

problem name so real

[@SmoothCode]

Can you please explain why a simple DFS method (without binary search) would not work to solve this problem? To me - all it seems to care about is the minimum absolute difference to get from 0,0 to the bottom right corner cell. Would you say it is impossible to use a DFS method to solve this problem? If so - please elaborate on why.

[@sk_4142]

I came up with a DFS backtracking solution, but it lead to a TLE, which makes sense since the solution would end up being O (3^(m*n)) time (not O(4^(m*n)) since we can't revisit a cell by moving backwards in a direction) because it would end up considering all paths from heights[0][0] to heights[m-1[n-1], which is very slow compared to Dijkstra's, which is O(m * n log(m *n)) time

[@rohanchess8332]

This looks very similar to the Prims algo, is it the same or is it different?

[@jesmigeorge4936]

can you please explain the problem 403. Frog Jump . I'm stuck on it. I know how to start but somehow I get stuck and not able to reach the solution.

[@johnsoto7112]

is a heap required to solve this problem?

[@tuandino6990]

You can do binary search combine with simple dfs/bfs

[@devkumar9889]

Please make today's video , it's very tough to understand

[@chitranshjawere4953]

isn't this just A* ?