Swim in Rising Water - Dijkstra's Algorithm - Leetcode 778 - Python

[@NeetCode]

💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc

[@algorithmo134]

Hi can you do inverse k pairs from leetcode daily challenge?

[@amitkhoth6672]

your explanations are very good but one thing is missing. Please do complexity analysis for each problem. I can see for some of the problems it is missing.

[@shrutikanetkar4189]

Thanks! Really appreciate your videos!

[@u2bacount]

Awesome explanation! Thanks! For anyone interested in a formal proof of correctness: The grid can be though of as a directed graph where the nodes are the cells in the grid, and nodes corresponding to adjacent cells are connected by edges. The weight of edge from u to v is the value of the cell corresponding to v in the grid. The total length of a path (as you mentioned) is the max weight of any edge along that path. If you check the proof of correctness in Dijkstras algorithm in CLRS you'll see that the only property of path length they use is that subpaths have length at most the length of the full path. This also why Dijsktras algorithm only works for non-negative edge weight graphs. The way length is measured in this problem (max edge weight along a path) satisfies the subpath property mentioned above, and hene Dijkstras algorithm can be used to find shortest distances with this measure of distance. Hope that helps someone :)

[@shalsteven]

what is CLRS?

[@MsNamaki]

@@shalsteven the algorithm book

[@stith_pragya]

Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@dheepthaaanand3214]

The difference between djikstras impl here and in Network Delay Time is that 1. There, we want to visit all the nodes to find the min weight to visit all. Here, we don't want to visit all nodes, just the optimal path to the bottom right 2. There, we can encounter a node as neighbour multiple times and when we process/visit it, we make note of the weight it took to get to it which will be minimum due to the heap. Here, we visit/process a neighbour node as soon as we encounter it, because the time it took to get to it is definitely going to be the minimum possible

[@aayushchhabra9805]

at 2:15 it should be t>=2 not t

[@NeetCode]

Yes that correct. I did the opposite by mistake.

[@Rahul-pr1zr]

Good explanation! One thing which I wasn't clear about though - How is adding a cell to the visited set as soon as it is first encountered ensuring that it need not be visited again? Can't it be a part of another path? I see the need to maintain visited within the same path but here it seems we're maintaining it globally.

[@NeetCode]

Good question. Since we are being greedy, every time we add a cell to Visit, we are guaranteeing that the path we took to get to this cell, has minimized the heights. In other words, if we visit Cell X and add it to the MinHeap and Visit Set, we are doing so because we know that there doesnt exist ANY other path in the entire grid, where the max height we had to take along the path, is any smaller. So we dont need to check every single path leading to Cell X, we only need to check the path where the Max Height is minimized.

[@ningzedai9052]

@@NeetCode If you rename the set from "visit" to "canBeSeen", it is much easier to understand.

[@amandaflood]

That cell is pushed to the heap and to the visited set at the same time. If it does form part of the solution path, the algorithm will find it at some point by popping it from the min heap. Put simply, the visited set keeps track of what's been pushed to the heap, so you don't push it twice.

[@shklbor]

in the tree of all paths currently explored, each path's value is the maximum height of cells forming it. due to the nature of the min heap, the minimum of these max values is discovered first. so the first time we encounter the current cell, we will have the minimum max value for it (which is what was required to mark it as visited), and hence don't need to visit this cell again from some other suboptimal path. p.s. the difference from standard shortest paths dijkstra, is that in it the tree of shortest paths is being maintained. the value of each path is distance which is cumulative and depends on all edge weights encountered in this path. a new short edge leading to current cell can be discovered later such that the cumulative distance to current cell is shorter. however, this can't happen when the value of path is the maximum height of a vertex (cell). even if a new vertex is discovered later on 'some other path' that has a height lesser than the max height of the 'first path' reaching the current cell, the 'some other path' is still constrained by its max height which is greater than 'first path's' max height (due to nature of the min heap) 🤯

[@dheepthaaanand3214]

Just to clarify the equality operations, we can move to an elevation of atmost t, meaning the elevation e has to be = e

[@mohammadkhan5430]

Just one thing: you can also keep the max for path in a different variable which will be your final answer. While constructing the min-heap just by the actual values of the grid. It will give the same answer.

[@Statemachine709]

2:00 t>= 2 not

[@ramvenkatachalam8153]

bro , u have to be a genius . my god . keep up the good work bro. Thanks .

[@kirillzlobin7135]

This is an amazing leetcode question

[@shalsteven]

Still don't understand why if we encouter the destination node for the first time, we can directly return it as the answer. For dijkstra algorithm, don't we have to visit all nodes first and then got the distance to the destination node by checking the value from the array of distance node from the starting node.

[@juheehong7445]

why does the placement of visited.add((r, c)) make a difference here? I tried it both ways (outside of the dr, dc for loop and within the for loop), and the first leads to TLE while the second passes with a decent result. Why do we have such a huge time difference?

[@jonnyskybrockett8844]

The first one takes longer because you only add processed points while the second one adds points which will be processed, meaning there’s a chance to have the same points in the minheap the first way, but that is eliminated completely the second way.

[@TheTheanith]

@@jonnyskybrockett8844 Your answer cleared that confusion up for me. Thank you.

[@prasad9012]

I came here to see if anybody else had the same question as I do lol. Thanks, Jonny.

[@sorenkarlesson5736]

Here's an alternative way: Binary search + dynamic programming 1. given a fixed water level, do dynamic programming to see if you can reach the end, this takes O(n^2) 2. do a binary search in the range of 0 to maximum of the grid, representing the range of possible water levels, each time perform step 1. Consequently you could find the smallest water level that you can reach the end. The range is log(n^2) ~ log(n) overall time complexity is O(n^2 logn)

[@nodarimosia6825]

Thanks for the hint (from over a year ago)! I solved it this way and it was way more intuitive than Dijkstra's algo for someone with limited experience in graph problems

[@jonaskhanwald566]

Excellent explanation as usual. Any problem which does not requires recursion seems easy to me. Recursion is so messy. I cant sort it out. Any tips to understand recursion !!!

[@RajSahaRks]

I would suggest solve easy questions and then debug them after solving to solidify your idea.

[@briankwon34]

Nice solution! Curious if it matters if we just calculate the max height aka the bottleneck everytime we pop off from the heap. Seems to work as well. Also, I think to check if a cell is in-bounds is more readable as row in range(N) for example. Great solution nonetheless

[@gaaligadu148]

great video as usual ! only missing thing is time and space complexity

[@abhishekpawar8458]

For anyone who is confused by the problem statement, my understanding here: There is no water flowing, at time t all elements in the matrix that are less than t now has a new value of t. All elements greater than t remain unchanged. So if your input is at t=0, then at time t=1 the elements are , at t=2 and finally at t=3

[@ChanChan-pg4wu]

Leetcode has ran out of good problems but make it tricky with the problem statement. Thanks for the explanation.

[@eidmone8684]

Just wanted to point out that this would be: let n = w * h Time: O(n*logn) since we are checking for visited values. If we did not have the visited set to check for duplicates then it would be O(n^2 * logn) Space: O(n) since at most we could have n values in our minHeap and n values in our visited set.

[@i_want_youtube_anonymity7099]

When I do the visit.add after the heappop, I get a time limit exceeded. but if I do it inside the neighbors loop then it passes all test cases quickly. Anyone know why?

[@mohakparekh8671]

Its already answered in the comments. Here is the explanantion given: The first one takes longer because you only add processed points while the second one adds points which will be processed, meaning there’s a chance to have the same points in the minheap the first way, but that is eliminated completely the second way.

[@Abhay14]

best explanation ever

[@kahafb]

class Solution: def swimInWater(self, grid: List[List[int]]) -> int: n, ans = len(grid), grid[-1][-1] dirs = [(0,-1), (0,1), (-1,0), (1,0)] heap = [(grid[0][0], 0, 0)] seen = set() while heap: val, i, j = heappop(heap) if i == j == n-1: return ans if (i, j) in seen: continue seen.add((i, j)) ans = max(ans, val) for dr, dc in dirs: inbounds = 0

[@amanseth540]

What's the difference between adding (r,c) when we pop from minHeap and adding it when adding to minHeap, the former gives TLE but the later got accepted. I didn't understand how it worked. If anyone has idea please reply back. The standard bfs says to add to visit set when we pop from the queue/minHeap but here it's changed and he didn't explained why this worked but not the other one.

[@halahmilksheikh]

That's incorrect. The standard BFS algorithm says you mark a node as visited when you enqueue, not when you dequeue. Check on wiki

[@asdfasyakitori8514]

Great video

[@mohammedghabyen721]

Great explanation, Thanks a lot

[@chaengsaltz829]

great explanation. Thank you very much. Keep up the good work!

[@shoooozzzz]

DIKE-STRA

[@kirillzlobin7135]

Woooooooooooooooooooooooooooowwwww :) This is amazing

[@kshegde3000]

can you suggest any good book to start dsa in python?

[@conorsmyth12358]

It's Dijkstra, my friend. That's an ij pronounced "eye". So it's D-eye-kstra :) Good explanation otherwise though.

[@sinnohperson8813]

This is the 78603th pronounciation I am hearing for it

[@pranavsharma7479]

follow up ques , Path With Minimum Effort

[@tachyon7777]

"Greater than" and "Less than" totally swapped. Made it so much confusing.

[@Mankind5490]

Shouldn't the values in the grid have to be all unique? The example that you did has duplicate values.

[@jonnyskybrockett8844]

Either way the solution is the same

[@sanjanar9198]

Nice

[@zaidshaikh2536]

Similar problem is 1631

[@ThePacemaker45]

Still dont get the problem statement at all

[@vikneshcs4824]

Why here dfs is not used

[@ashkan.arabim]

fyi: it's pronounced "dykstra". "j" in dutch is like "y".

[@CalrosACJ55]

djikstra

[@PedanticAnswerSeeker]

This problem has one of the worst descriptions on leetcode

[@chenjus]

why is that problem marked as hard?

[@Mikeymikers1]

could u solve it on your own? this seems like it could be a matrix or DP problem if you didn't read the title of the video

[@suvajitchakrabarty]

There is almost zero chance someone can come up with this algorithm by their own in a timed interview.

[@prasad9012]

Implementing Dijkstra's is easy but reaching the idea that Dijkstra's is applicable here doesn't seem that easy to me

[@suvajitchakrabarty]

@@brandonwisco Your CS program will teach you this algorithm, no doubt. I wouldn't say shortest path is a fundamental concept of CS. You don't need it in most daily programming tasks. Also, in my initial comment, I was talking about the algorithm for the question itself and not Dijkstra's algorithm.

[@tsunghan_yu]

3:30 Can you spell and pronounce it right? Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz)