Swim in Rising Water

• LeetCode

• You do not need to keep track of t, because we can swim infinite distances in zero time
• If you notice Example 2, in the path, the answer is the highest elevation in the path.
  • So what the question is asking us is what's the path we can take that minimizes the height
• Use Dijkstra's Shortest Path Algorithm
• The only limitation is the height of the current grid cell we're at- the time is not important. Just do a DFS traversal while keeping in mind that the cost to travel to any node in the graph is the maximum elevation seen until that point. For Example 2, this would be 16.
• Remember to add elements to a visited set during the neighbor search, and not outside when you're popping from the min heap. This is because if you're adding to visited when popping from the min heap, there is a chance for the same grid cell to be enqueued twice, because there was a different way of reaching it through a different node.
  • NeetCode's comment on why we mark a cell as visited immediately:
    • 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 doesn't exist ANY other path in the entire grid, where the max height we had to take along the path, is any smaller. So we don't need to check every single path leading to Cell X, we only need to check the path where the Max Height is minimized.

Show less